Matroid theory has been developed to be a mature branch of mathematics and has extensive applications in combinatorial optimization,algorithm design and so *** the other hand,quantumcomputing has attracted much atten...
详细信息
Matroid theory has been developed to be a mature branch of mathematics and has extensive applications in combinatorial optimization,algorithm design and so *** the other hand,quantumcomputing has attracted much attention and has been shown to surpass classical computing on solving some computational ***,crossover studies of the two fields seem to be missing in the *** paper initiates the study of quantum algorithms for matroid property *** is shown that quadratic quantum speedup is possible for the calculation problem of finding the girth or the number of circuits(bases,flats,hyperplanes)of a matroid,and for the decision problem of deciding whether a matroid is uniform or Eulerian,by giving a uniform lower boundΩ■on the query complexity of all these *** the other hand,for the uniform matroid decision problem,an asymptotically optimal quantum algorithm is proposed which achieves the lower bound,and for the girth problem,an almost optimal quantum algorithm is given with query complexityO■.In addition,for the paving matroid decision problem,a lower boundΩ■on the query complexity is obtained,and an O■ quantum algorithm is presented.
The query model(or black-box model)has attracted much attention from the communities of both classical and quantum ***,quantum advantages are revealed by presenting a quantum algorithm that has a better query complexi...
详细信息
The query model(or black-box model)has attracted much attention from the communities of both classical and quantum ***,quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical *** the history of quantum algorithms,the Deutsch algorithm and the Deutsch-Jozsa algorithm play a fundamental role and both are exact one-query quantum *** leads us to con-sider the problem:what functions can be computed by exact one-query quantum algorithms?This problem has been ad-dressed in the literature for total Boolean functions and symmetric partial Boolean functions,but is still open for general partial Boolean ***,in this paper,we continue to characterize the computational power of exact one-query quantum algorithms for general partial Boolean ***,we present several necessary and sufficient conditions for a partial Boolean function to be computed by exact one-query quantum ***,inspired by these conditions,we discover some new representative functions that can be computed by exact one-query quantum algorithms but have an essential difference from the already known ***,it is worth pointing out that before our work,the known func-tions that can be computed by exact one-query quantum algorithms are all symmetric functions and the quantum algo-rithm used is essentially the Deutsch-Jozsa algorithm,whereas the functions discovered in this paper are generally asym-metric and new algorithms to compute these functions are ***,this expands the class of functions that can be computed by exact one-query quantum algorithms.
Distributed quantum computation has gained extensive *** this paper,we consider a search problem that includes only one target item in the unordered *** that,we propose a distributed exact Grover’s algorithm(DEGA),wh...
详细信息
Distributed quantum computation has gained extensive *** this paper,we consider a search problem that includes only one target item in the unordered *** that,we propose a distributed exact Grover’s algorithm(DEGA),which decomposes the original search problem into■n/2■***,(i)our algorithm is as exact as the modified version of Grover’s algorithm by Long,which means the theoretical probability of finding the objective state is 100%;(ii)the actual depth of our circuit is 8(n mod 2)+9,which is less than the circuit depths of the original and modified Grover’s algorithms,1+8■π/4√2^(n)■and 9+8■π/4√2^(n)-1/2■,*** only depends on the parity of n,and it is not deepened as n increases;(iii)we provide particular situations of the DEGA on Mindquantum(a quantum software)to demonstrate the practicality and validity of our *** our circuit is shallower,it will be more resistant to the depolarization channel noise.
We study the impact of quantum computation on the fundamental problem of testing the property of distributions. In particular, we focus on testing whether two unknown classical distributions are close or far enough, a...
详细信息
This work revisits quantum algorithms for the well-known welded tree problem, proposing a very succinct quantum algorithm based on the simplest coined quantum walks. It simply iterates the naturally defined coined qua...
详细信息
The element distinctness problem is to determine whether a string of $N$ elements, i.e. $x=(x_1,\ldots,x_N)$ where $x_i\in \{1,\ldots,M\}$ and $M\geq N$, contains two elements of the same value (a.k.a colliding pair),...
详细信息
As industrial models and designs grow increasingly complex, the demand for optimal control of large-scale dynamical systems has significantly increased. However, traditional methods for optimal control incur significa...
There has been a very large body of research on searching a marked vertex on a graph based on quantum walks, and Grover's algorithm can be regarded as a quantum walk-based search algorithm on a special graph. Howe...
详细信息
There has been a very large body of research on searching a marked vertex on a graph based on quantum walks, and Grover's algorithm can be regarded as a quantum walk-based search algorithm on a special graph. However, the existing quantum walk-based search algorithms suffer severely from the soufflé problem, which mainly means that the success probability of finding a marked vertex could shrink dramatically, even to zero, when the number of search steps is greater than the right one, thus heavily reducing the robustness and practicability of the algorithm. Surprisingly, while the soufflé problem of Grover's algorithm has attracted enough attention, how to address this problem for general quantum walk-based search algorithms is missing in the literature. Here we initiate the study of overcoming the soufflé problem for quantum walk-based search algorithms by presenting a quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup. In this framework, for any adjustable parameter ε, the quantum algorithm can find a marked vertex on an N-vertex complete bipartite graph with probability at least 1−ε, whenever the number of search steps h satisfies h≥ln(2ε)N+1. Note that the algorithm need not know the exact number of marked vertices. Consequently, we obtain quantum search algorithms with stronger robustness and practicability.
We conduct a systematic study of quantum circuits composed of multiple-control Z-rotation (MCZR) gates as primitives, since they are widely-used components in quantum algorithms and also have attracted much experiment...
详细信息
A commercial quantum key distribution (QKD) system needs to be formally certified to enable its wide deployment. The certification should include the system’s robustness against known implementation loopholes and att...
详细信息
A commercial quantum key distribution (QKD) system needs to be formally certified to enable its wide deployment. The certification should include the system’s robustness against known implementation loopholes and attacks that exploit them. Here we ready a fiber-optic QKD system for this procedure. The system has a prepare-and-measure scheme with decoy-state BB84 protocol, polarization encoding, a qubit source rate of 312.5 MHz, and is manufactured by QRate. We detail its hardware and postprocessing. We analyze the hardware for known implementation loopholes, search for possible new loopholes, and discuss countermeasures. We then amend the system design to address the highest-risk loopholes identified. We also work out technical requirements on the certification lab and outline its possible structure.
暂无评论