BQP
Template:Short descriptionTemplate:About
In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.<ref name="Chuang2000">Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. Template:Isbn.</ref> It is the quantum analogue to the complexity class BPP.
A decision problem is a member of BQP if there exists a quantum algorithm (an algorithm that runs on a quantum computer) that solves the decision problem with high probability and is guaranteed to run in polynomial time. A run of the algorithm will correctly solve the decision problem with a probability of at least 2/3.
| BQP algorithm (1 run) | ||
|---|---|---|
| Template:Diagonal split header | Template:Yes | Template:No |
| Template:Yes | ≥ 2/3 | ≤ 1/3 |
| Template:No | ≤ 1/3 | ≥ 2/3 |
| BQP algorithm (k runs) | ||
| Template:Diagonal split header | Template:Yes | Template:No |
| Template:Yes | > 1 − 2−ck | < 2−ck |
| Template:No | < 2−ck | > 1 − 2−ck |
| for some constant c > 0 | ||
DefinitionEdit
BQP can be viewed as the languages associated with certain bounded-error uniform families of quantum circuits.<ref name=Chuang2000/> A language L is in BQP if and only if there exists a polynomial-time uniform family of quantum circuits <math>\{Q_n\colon n \in \mathbb{N}\}</math>, such that
- For all <math>n \in \mathbb{N}</math>, Qn takes n qubits as input and outputs 1 bit
- For all x in L, <math>\mathrm{Pr}(Q_{|x|}(x)=1)\geq \tfrac{2}{3}</math>
- For all x not in L, <math>\mathrm{Pr}(Q_{|x|}(x)=0)\geq \tfrac{2}{3}</math>
Alternatively, one can define BQP in terms of quantum Turing machines. A language L is in BQP if and only if there exists a polynomial quantum Turing machine that accepts L with an error probability of at most 1/3 for all instances.<ref name="BernVazi">Template:Cite journal</ref>
Similarly to other "bounded error" probabilistic classes, the choice of 1/3 in the definition is arbitrary. We can run the algorithm a constant number of times and take a majority vote to achieve any desired probability of correctness less than 1, using the Chernoff bound. The complexity class is unchanged by allowing error as high as 1/2 − n−c on the one hand, or requiring error as small as 2−nc on the other hand, where c is any positive constant, and n is the length of input.<ref>Template:Cite book</ref>
Relationship to other complexity classesEdit
BQP is defined for quantum computers; the corresponding complexity class for classical computers (or more formally for probabilistic Turing machines) is BPP. Just like P and BPP, BQP is low for itself, which means Template:Math.<ref name="BernVazi"/> Informally, this is true because polynomial time algorithms are closed under composition. If a polynomial time algorithm calls polynomial time algorithms as subroutines, the resulting algorithm is still polynomial time.
BQP contains P and BPP and is contained in AWPP,<ref>Template:Cite journal</ref> PP<ref>L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.</ref> and PSPACE.<ref name=BernVazi/> In fact, BQP is low for PP, meaning that a PP machine achieves no benefit from being able to solve BQP problems instantly, an indication of the possible difference in power between these similar classes. The known relationships with classic complexity classes are:
- <math>\mathsf{P \subseteq BPP \subseteq BQP\subseteq AWPP \subseteq PP \subseteq PSPACE\subseteq EXP}</math>
As the problem of Template:Tmath has not yet been solved, the proof of inequality between BQP and classes mentioned above is supposed to be difficult.<ref name="BernVazi" /> The relation between BQP and NP is not known. In May 2018, computer scientists Ran Raz of Princeton University and Avishay Tal of Stanford University published a paper<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> which showed that, relative to an oracle, BQP was not contained in PH. It can be proven that there exists an oracle A such that <math>\mathsf{BQP}^\mathrm{A}\nsubseteq\mathsf{PH}^\mathrm{A}</math>.<ref name=":0" /> In an extremely informal sense, this can be thought of as giving PH and BQP an identical, but additional, capability and verifying that BQP with the oracle (BQPA) can do things PHA cannot. While an oracle separation has been proven, the fact that BQP is not contained in PH has not been proven. An oracle separation does not prove whether or not complexity classes are the same. The oracle separation gives intuition that BQP may not be contained in PH.
It has been suspected for many years that Fourier Sampling is a problem that exists within BQP, but not within the polynomial hierarchy. Recent conjectures have provided evidence that a similar problem, Fourier Checking, also exists in the class BQP without being contained in the polynomial hierarchy. This conjecture is especially notable because it suggests that problems existing in BQP could be classified as harder than NP-Complete problems. Paired with the fact that many practical BQP problems are suspected to exist outside of P (it is suspected and not verified because there is no proof that P ≠ NP), this illustrates the potential power of quantum computing in relation to classical computing.<ref name=":0">Template:Cite journal</ref>
Adding postselection to BQP results in the complexity class PostBQP which is equal to PP.<ref name="PostBQP=PP">Template:Cite journal. Preprint available at [1]</ref><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
A complete problem for Promise-BQPEdit
Promise-BQP is the class of promise problems that can be solved by a uniform family of quantum circuits (i.e., within BQP).<ref name="janzing-wocjan">Template:Cite journal</ref> Completeness proofs focus on this version of BQP. Similar to the notion of NP-completeness and other complete problems, we can define a complete problem as a problem that is in Promise-BQP and that every other problem in Promise-BQP reduces to it in polynomial time.
APPROX-QCIRCUIT-PROBEdit
The APPROX-QCIRCUIT-PROB problem is complete for efficient quantum computation, and the version presented below is complete for the Promise-BQP complexity class (and not for the total BQP complexity class, for which no complete problems are known). APPROX-QCIRCUIT-PROB's completeness makes it useful for proofs showing the relationships between other complexity classes and BQP.
Given a description of a quantum circuit Template:Mvar acting on Template:Mvar qubits with Template:Mvar gates, where Template:Mvar is a polynomial in Template:Mvar and each gate acts on one or two qubits, and two numbers <math>\alpha, \beta \in [0,1], \alpha > \beta</math>, distinguish between the following two cases:
- measuring the first qubit of the state <math>C|0\rangle^{\otimes n}</math> yields <math>|1\rangle</math> with probability <math>\geq \alpha</math>
- measuring the first qubit of the state <math>C|0\rangle^{\otimes n}</math> yields <math>|1\rangle</math> with probability <math>\leq \beta</math>
Here, there is a promise on the inputs as the problem does not specify the behavior if an instance is not covered by these two cases.
Claim. Any BQP problem reduces to APPROX-QCIRCUIT-PROB.
Proof. Suppose we have an algorithm Template:Mvar that solves APPROX-QCIRCUIT-PROB, i.e., given a quantum circuit Template:Mvar acting on Template:Mvar qubits, and two numbers <math>\alpha, \beta \in [0,1], \alpha > \beta</math>, Template:Mvar distinguishes between the above two cases. We can solve any problem in BQP with this oracle, by setting <math>\alpha = 2/3, \beta = 1/3</math>.
For any <math>L \in \mathsf{BQP} </math>, there exists family of quantum circuits <math>\{Q_n\colon n \in \mathbb{N}\}</math> such that for all <math>n \in \mathbb{N}</math>, a state <math> |x\rangle </math> of <math>n </math> qubits, if <math>x \in L, Pr(Q_n(|x\rangle)=1) \geq 2/3</math>; else if <math>x \notin L, Pr(Q_n(|x\rangle)=0) \geq 2/3 </math>. Fix an input <math> |x\rangle </math> of Template:Mvar qubits, and the corresponding quantum circuit <math>Q_n</math>. We can first construct a circuit <math>C_x</math> such that <math>C_x|0\rangle^{\otimes n} = |x\rangle</math>. This can be done easily by hardwiring <math> |x\rangle </math> and apply a sequence of CNOT gates to flip the qubits. Then we can combine two circuits to get <math>C' = Q_nC_x</math>, and now <math>C'|0\rangle^{\otimes n} = Q_n|x\rangle</math>. And finally, necessarily the results of <math>Q_n</math> is obtained by measuring several qubits and apply some (classical) logic gates to them. We can always defer the measurement<ref name="NielsenChuang2010">Template:Cite book</ref><ref name="Cross2012">Template:Cite book</ref> and reroute the circuits so that by measuring the first qubit of <math>C'|0\rangle^{\otimes n} = Q_n|x\rangle</math>, we get the output. This will be our circuit Template:Mvar, and we decide the membership of <math>x \in L</math> by running <math>A(C)</math> with <math>\alpha = 2/3, \beta = 1/3</math>. By definition of BQP, we will either fall into the first case (acceptance), or the second case (rejection), so <math>L \in \mathsf{BQP} </math> reduces to APPROX-QCIRCUIT-PROB.
BQP and EXPEdit
We begin with an easier containment. To show that <math>\mathsf{BQP} \subseteq \mathsf{EXP}</math>, it suffices to show that APPROX-QCIRCUIT-PROB is in EXP since APPROX-QCIRCUIT-PROB is BQP-complete.
Note that this algorithm also requires <math>2^{O(n)}</math> space to store the vectors and the matrices. We will show in the following section that we can improve upon the space complexity.
BQP and PSPACEEdit
Sum of histories is a technique introduced by physicist Richard Feynman for path integral formulation. APPROX-QCIRCUIT-PROB can be formulated in the sum of histories technique to show that <math>\mathsf{BQP} \subseteq \mathsf{PSPACE}</math>.<ref>E. Bernstein and U. Vazirani. Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997.</ref>
Consider a quantum circuit Template:Mvar, which consists of Template:Mvar gates, <math>g_1, g_2, \cdots, g_m</math>, where each <math>g_j</math> comes from a universal gate set and acts on at most two qubits. To understand what the sum of histories is, we visualize the evolution of a quantum state given a quantum circuit as a tree. The root is the input <math>|0\rangle^{\otimes n}</math>, and each node in the tree has <math>2^n</math> children, each representing a state in <math>\mathbb C^n</math>. The weight on a tree edge from a node in Template:Mvar-th level representing a state <math>|x\rangle</math> to a node in <math>j+1</math>-th level representing a state <math>|y\rangle</math> is <math>\langle y|g_{j+1}|x\rangle</math>, the amplitude of <math>|y\rangle</math> after applying <math>g_{j+1}</math> on <math>|x\rangle</math>. The transition amplitude of a root-to-leaf path is the product of all the weights on the edges along the path. To get the probability of the final state being <math>|\psi\rangle</math>, we sum up the amplitudes of all root-to-leave paths that ends at a node representing <math>|\psi\rangle</math>.
More formally, for the quantum circuit Template:Mvar, its sum over histories tree is a tree of depth Template:Mvar, with one level for each gate <math>g_i</math> in addition to the root, and with branching factor <math>2^n</math>.
Notice in the sum over histories algorithm to compute some amplitude <math>\alpha_x</math>, only one history is stored at any point in the computation. Hence, the sum over histories algorithm uses <math>O(nm)</math> space to compute <math>\alpha_x</math> for any Template:Mvar since <math>O(nm)</math> bits are needed to store the histories in addition to some workspace variables.
Therefore, in polynomial space, we may compute <math>\sum_x |\alpha_x|^2</math> over all Template:Mvar with the first qubit being Template:Val, which is the probability that the first qubit is measured to be 1 by the end of the circuit.
Notice that compared with the simulation given for the proof that <math>\mathsf{BQP} \subseteq \mathsf{EXP}</math>, our algorithm here takes far less space but far more time instead. In fact it takes <math>O(m\cdot 2^{mn} )</math> time to calculate a single amplitude!
BQP and PPEdit
A similar sum-over-histories argument can be used to show that <math>\mathsf{BQP} \subseteq \mathsf{PP}</math>. <ref> L. Adleman, J. DeMarrais, and M. Huang. Quantum computability, SIAM Journal on Comput- ing 26:1524-1540, 1997.</ref>
P and BQP Template:AnchorEdit
We know <math> \mathsf{P} \subseteq \mathsf{BQP} </math>, since every classical circuit can be simulated by a quantum circuit. <ref> Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR 1796805.</ref>
It is conjectured that BQP solves hard problems outside of P, specifically, problems in NP. The claim is indefinite because we don't know if P=NP, so we don't know if those problems are actually in P. Below are some evidence of the conjecture:
- Integer factorization (see Shor's algorithm)<ref name="Shor">arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor</ref>
- Discrete logarithm<ref name="Shor"/>
- Simulation of quantum systems (see universal quantum simulator)
- Approximating the Jones polynomial at certain roots of unity
- Harrow-Hassidim-Lloyd (HHL) algorithm
See alsoEdit
- Hidden subgroup problem
- Polynomial hierarchy (PH)
- Quantum complexity theory
- QMA, the quantum equivalent to NP.
- QIP, the quantum equivalent to IP.