Movatterモバイル変換

[0]ホーム

Jump to content

BQP

Edit links

From Wikipedia, the free encyclopedia

Computational complexity class of problems

This article is about the computational complexity class. For other uses, seeBQP (disambiguation).

Diagram of randomised complexity classes — BQP in relation to other probabilistic complexity classes (ZPP,RP, co-RP,BPP,PP), which generaliseP withinPSPACE. It is unknown if any of these containments are strict.

Incomputational complexity theory,bounded-error quantum polynomial time (BQP) is the class ofdecision problems solvable by aquantum computer inpolynomial time, with an error probability of at most 1/3 for all instances.^[1] It is the quantum analogue to thecomplexity classBPP.

A decision problem is a member ofBQP if there exists aquantum algorithm (analgorithm that runs on a quantum computer) that solves the decision problemwith 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)
Answer produced Correct answer	Yes	No
Yes	≥ 2/3	≤ 1/3
No	≤ 1/3	≥ 2/3
BQP algorithm (k runs)
Answer produced Correct answer	Yes	No
Yes	> 1 − 2^−ck	< 2^−ck
No	< 2^−ck	> 1 − 2^−ck
for some constantc > 0

Definition

[edit]

BQP can be viewed as thelanguages associated with certain bounded-error uniform families ofquantum circuits.^[1] A languageL is inBQP if and only if there exists apolynomial-time uniform family of quantum circuits $\{Q_{n}\colon n\in \mathbb {N} \}$ , such that

For all $n\in \mathbb {N}$ ,Q_n takesnqubits as input and outputs 1bit
For allx inL, $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$
For allx not inL, $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$

Alternatively, one can defineBQP in terms ofquantum Turing machines. A languageL is inBQP if and only if there exists a polynomial quantum Turing machine that acceptsL with an error probability of at most 1/3 for all instances.^[2]

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 theChernoff 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^{−n^c} on the other hand, wherec is any positive constant, andn is the length of input.^[3]

Relationship to other complexity classes

[edit]

Unsolved problem in computer science

What is the relationship between

{\mathsf {BQP}}

and

{\mathsf {NP}}

More unsolved problems in computer science

The suspected relationship ofBQP to other problem spaces^[1]

BQP is defined for quantum computers; the corresponding complexity class for classical computers (or more formally forprobabilistic Turing machines) isBPP. Just likeP andBPP,BQP islow for itself, which meansBQP^BQP = BQP.^[2] 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 containsP andBPP and is contained inAWPP,^[4]PP^[5] andPSPACE.^[2]In fact,BQP islow forPP, meaning that aPP machine achieves no benefit from being able to solveBQP problems instantly, an indication of the possible difference in power between these similar classes. The known relationships with classic complexity classes are:

{\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}}

As the problem of⁠ ${\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}$ ⁠ has not yet been solved, the proof of inequality betweenBQP and classes mentioned above is supposed to be difficult.^[2] The relation betweenBQP andNP is not known. In May 2018, computer scientistsRan Raz ofPrinceton University and Avishay Tal ofStanford University published a paper^[6] which showed that, relative to anoracle, BQP was not contained inPH. It can be proven that there exists an oracle A such that ${\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }$ .^[7] 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 (BQP^A) can do things PH^A 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 thepolynomial hierarchy. This conjecture is especially notable because it suggests that problems existing in BQP could be classified as harder thanNP-Complete problems. Paired with the fact that many practical BQP problems are suspected to exist outside ofP (it is suspected and not verified because there is no proof thatP ≠ NP), this illustrates the potential power of quantum computing in relation to classical computing.^[7]

Addingpostselection toBQP results in the complexity classPostBQP which is equal toPP.^[8]^[9]

A complete problem for Promise-BQP

[edit]

Promise-BQP is the class ofpromise problems that can be solved by a uniform family of quantum circuits (i.e., within BQP).^[10] Completeness proofs focus on this version of BQP. Similar to the notion ofNP-completeness and othercomplete 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-PROB

[edit]

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 circuitC acting onn qubits withm gates, wherem is a polynomial inn and each gate acts on one or two qubits, and two numbers $\alpha ,\beta \in [0,1],\alpha >\beta$ , distinguish between the following two cases:

measuring the first qubit of the state $C|0\rangle ^{\otimes n}$ yields $|1\rangle$ with probability $\geq \alpha$
measuring the first qubit of the state $C|0\rangle ^{\otimes n}$ yields $|1\rangle$ with probability $\leq \beta$

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 algorithmA that solves APPROX-QCIRCUIT-PROB, i.e., given a quantum circuitC acting onn qubits, and two numbers $\alpha ,\beta \in [0,1],\alpha >\beta$ ,A distinguishes between the above two cases. We can solve any problem in BQP with this oracle, by setting $\alpha =2/3,\beta =1/3$ .

For any $L\in {\mathsf {BQP}}$ , there exists family of quantum circuits $\{Q_{n}\colon n\in \mathbb {N} \}$ such that for all $n\in \mathbb {N}$ , a state $|x\rangle$ of $n {\displaystyle n}$ qubits, if $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ ; else if $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ . Fix an input $|x\rangle$ ofn qubits, and the corresponding quantum circuit $Q_{n}$ . We can first construct a circuit $C_{x}$ such that $C_{x}|0\rangle ^{\otimes n}=|x\rangle$ . This can be done easily by hardwiring $|x\rangle$ and apply a sequence ofCNOT gates to flip the qubits. Then we can combine two circuits to get $C'=Q_{n}C_{x}$ , and now $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ . And finally, necessarily the results of $Q_{n}$ is obtained by measuring several qubits and apply some (classical) logic gates to them. We can alwaysdefer the measurement^[11]^[12] and reroute the circuits so that by measuring the first qubit of $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ , we get the output. This will be our circuitC, and we decide the membership of $x\in L$ by running $A(C)$ with $\alpha =2/3,\beta =1/3$ . By definition of BQP, we will either fall into the first case (acceptance), or the second case (rejection), so $L\in {\mathsf {BQP}}$ reduces to APPROX-QCIRCUIT-PROB.

BQP and EXP

[edit]

We begin with an easier containment. To show that ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ , it suffices to show that APPROX-QCIRCUIT-PROB is in EXP since APPROX-QCIRCUIT-PROB is BQP-complete.

Claim— ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}$

Proof

The idea is simple. Since we have exponential power, given a quantum circuitC, we can use classical computer to stimulate each gate inC to get the final state.

More formally, letC be a polynomial sized quantum circuit onn qubits andm gates, where m is polynomial in n. Let $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ and $|\psi _{i}\rangle$ be the state after thei-th gate in the circuit is applied to $|\psi _{i-1}\rangle$ . Each state $|\psi _{i}\rangle$ can be represented in a classical computer as a unit vector in $\mathbb {C} ^{2^{n}}$ . Furthermore, each gate can be represented by a matrix in $\mathbb {C} ^{2^{n}\times 2^{n}}$ . Hence, the final state $|\psi _{m}\rangle$ can be computed in $O(m\cdot 2^{2n})$ time, and therefore all together, we have an $2^{O(n)}$ time algorithm for calculating the final state, and thus the probability that the first qubit is measured to be one. This implies that ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}$ .

Note that this algorithm also requires $2^{O(n)}$ 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 PSPACE

[edit]

Sum of histories is a technique introduced by physicistRichard Feynman forpath integral formulation. APPROX-QCIRCUIT-PROB can be formulated in the sum of histories technique to show that ${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$ .^[13]

Consider a quantum circuitC, which consists oft gates, $g_{1},g_{2},\cdots ,g_{m}$ , where each $g_{j}$ comes from auniversal 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 $|0\rangle ^{\otimes n}$ , and each node in the tree has $2^{n}$ children, each representing a state in $\mathbb {C} ^{n}$ . The weight on a tree edge from a node inj-th level representing a state $|x\rangle$ to a node in $j+1$ -th level representing a state $|y\rangle$ is $\langle y|g_{j+1}|x\rangle$ , the amplitude of $|y\rangle$ after applying $g_{j+1}$ on $|x\rangle$ . 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 $|\psi \rangle$ , we sum up the amplitudes of all root-to-leave paths that ends at a node representing $|\psi \rangle$ .

More formally, for the quantum circuitC, its sum over histories tree is a tree of depthm, with one level for each gate $g_{i}$ in addition to the root, and with branching factor $2^{n}$ .

Define—A history is a path in the sum of histories tree. We will denote a history by a sequence $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ for some final statex.

Define—Let $u,v\in \{0,1\}^{n}$ . Let amplitude of the edge $(|u\rangle ,|v\rangle )$ in thej-th level of the sum over histories tree be $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ . For any history $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ , the transition amplitude of the history is the product $\alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)$ .

Claim—For a history $(u_{0}\rightarrow \cdots \rightarrow u_{m})$ . The transition amplitude of the history is computable in polynomial time.

Proof

Each gate $g_{j}$ can be decomposed into $g_{j}=I\otimes {\tilde {g}}_{j}$ for some unitary operator ${\tilde {g}}_{j}$ acting on two qubits, which without loss of generality can be taken to be the first two. Hence, $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ which can be computed in polynomial time inn. Sincem is polynomial inn, the transition amplitude of the history can be computed in polynomial time.

Claim—Let $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ be the final state of the quantum circuit. For some $x\in \{0,1\}^{n}$ , the amplitude $\alpha _{x}$ can be computed by $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ .

Proof

We have $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ . The result comes directly by inserting $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ between $g_{1},g_{2}$ , and $g_{2},g_{3}$ , and so on, and then expand out the equation. Then each term corresponds to a $\alpha _{h}$ , where $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$

Claim— ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {PSPACE}}$

Notice in the sum over histories algorithm to compute some amplitude $\alpha _{x}$ , only one history is stored at any point in the computation. Hence, the sum over histories algorithm uses $O(nm)$ space to compute $\alpha _{x}$ for anyx since $O(nm)$ bits are needed to store the histories in addition to some workspace variables.

Therefore, in polynomial space, we may compute $\sum _{x}|\alpha _{x}|^{2}$ over allx with the first qubit being1, 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 ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ , our algorithm here takes far less space but far more time instead. In fact it takes $O(m\cdot 2^{mn})$ time to calculate a single amplitude!

BQP and PP

[edit]

A similar sum-over-histories argument can be used to show that ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$ .^[14]

P and BQP

[edit]

We know ${\mathsf {P}}\subseteq {\mathsf {BQP}}$ , since every classical circuit can be simulated by a quantum circuit.^[15]

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 (seeShor's algorithm)^[16]
Discrete logarithm^[16]
Simulation of quantum systems (seeuniversal quantum simulator)
Approximating theJones polynomial at certain roots of unity
Harrow-Hassidim-Lloyd (HHL) algorithm

References

[edit]

^^a ^b ^cMichael Nielsen and Isaac Chuang (2000).Quantum Computation and Quantum Information. Cambridge: Cambridge University Press.ISBN 0-521-63503-9.
^^a ^b ^c ^dBernstein, Ethan; Vazirani, Umesh (October 1997). "Quantum Complexity Theory".SIAM Journal on Computing.26 (5):1411–1473.CiteSeerX 10.1.1.655.1186.doi:10.1137/S0097539796300921.
^Barak, Sanjeev Arora, Boaz (2009).Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak. Cambridge. p. 122. Retrieved24 July 2018.{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: multiple names: authors list (link)
^Fortnow, Lance; Rogers, John (1999)."Complexity limitations on Quantum computation"(PDF).J. Comput. Syst. Sci.59 (2):240–252.arXiv:cs/9811023.doi:10.1006/jcss.1999.1651.ISSN 0022-0000.S2CID 42516312.Archived(PDF) from the original on 2022-10-09.
^L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput.,26(5):1524–1540, 1997.
^George, Michael Goderbauer, Stefan."ECCC - TR18-107".eccc.weizmann.ac.il. Retrieved2018-08-03.{{cite web}}: CS1 maint: multiple names: authors list (link)
^^a ^bAaronson, Scott (2010)."BQP and the Polynomial Hierarchy"(PDF).Proceedings of ACM STOC 2010.Archived(PDF) from the original on 2022-10-09.
^Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time".Proceedings of the Royal Society A.461 (2063):3473–3482.arXiv:quant-ph/0412187.Bibcode:2005RSPSA.461.3473A.doi:10.1098/rspa.2005.1546.S2CID 1770389.. Preprint available at[1]
^Aaronson, Scott (2004-01-11)."Complexity Class of the Week: PP".Computational Complexity Weblog. Retrieved2008-05-02.
^Janzing, Dominik; Wocjan, Pawel (2007-03-30)."A Simple PromiseBQP-complete Matrix Problem"(PDF).Theory of Computing.3 (4):61–79.doi:10.4086/toc.2007.v003a004. Retrieved2024-04-18.
^Michael A. Nielsen; Isaac L. Chuang (9 December 2010). "4.4 Measurement".Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. p. 186.ISBN 978-1-139-49548-6.
^Odel A. Cross (5 November 2012). "5.2.2 Deferred Measurement".Topics in Quantum Computing. O. A. Cross. p. 348.ISBN 978-1-4800-2749-7.
^E. Bernstein and U. Vazirani. Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997.
^ L. Adleman, J. DeMarrais, and M. Huang. Quantum computability, SIAM Journal on Comput- ing 26:1524-1540, 1997.
^ Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR 1796805.
^^a ^barXiv:quant-ph/9508027v2Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

External links

[edit]

Complexity Zoo link to BQP Archived 2013-06-03 at theWayback Machine

Quantum information science

General

Theorems

Quantum
communication

Quantum cryptography	Hidden matching Post-quantum cryptography Quantum coin flipping Quantum money Quantum key distribution BB84 SARG04 other protocols Quantum secret sharing

Quantum algorithms

Quantum
complexity theory

Quantum
processor benchmarks

Quantum
computing models

Quantum
error correction

Physical
implementations

Quantum optics	Cavity QED Circuit QED Linear optical QC KLM protocol
Ultracold atoms	Neutral atom QC Trapped-ion QC
Spin-based	Kane QC Spin qubit QC NV center NMR QC
Superconducting	Charge qubit Flux qubit Phase qubit Transmon

Quantum
programming

v t e Complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC TC⁰ L SL RL FL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete TFNP FNP AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY NONELEMENTARY PR R RE ALL
Other complexity classes	polyL QP
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
List of complexity classes