Klassen av språk som lar seg gjenkjenne av kvante-polynomtidalgoritmer. Har: [[BQP]] $\subseteq$ [[PSPACE]]. Formodning: [[NP snitt coNP]] $\subseteq$ [[BQP]]. Fra [Complexity Zoo](https://complexityzoo.net/Complexity_Zoo:B#bqp): > The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error. > > One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error ([Yao93](https://complexityzoo.net/Zooref#yao93)). Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97](https://complexityzoo.net/Zooref#adh97)). > > BQP is often identified as the class of feasible problems for quantum computers. > > Contains the [factoring](https://complexityzoo.net/Complexity_Garden#integer_factorization) and [discrete logarithm](https://complexityzoo.net/Complexity_Garden#discrete_logarithm) problems ([Sho97](https://complexityzoo.net/Zooref#sho97)), the hidden Legendre symbol problem ([DHI02](https://complexityzoo.net/Zooref#dhi02)), the Pell's equation and principal ideal problems ([Hal02](https://complexityzoo.net/Zooref#hal02)), and some other problems not thought to be in [BPP](https://complexityzoo.net/Complexity_Zoo:B#bpp). > > Defined in [BV97](https://complexityzoo.net/Zooref#bv97), where it is also shown that BQP contains [BPP](https://complexityzoo.net/Complexity_Zoo:B#bpp) and is contained in [P](https://complexityzoo.net/Complexity_Zoo:P#p "Complexity Zoo:P") with a [sharpP](https://complexityzoo.net/Complexity_Zoo:Symbols#sharpp) oracle. > > BQP$^{\text{BQP}}$ = BQP ([BV97](https://complexityzoo.net/Zooref#bv97)). > > [ADH97](https://complexityzoo.net/Zooref#adh97) showed that BQP is contained in [PP](https://complexityzoo.net/Complexity_Zoo:P#pp), and [FR98](https://complexityzoo.net/Zooref#fr98) showed that BQP is contained in [AWPP](https://complexityzoo.net/Complexity_Zoo:A#awpp). > > There exist oracles relative to which: > > - BQP does not equal to [BPP](https://complexityzoo.net/Complexity_Zoo:B#bpp) ([BV97](https://complexityzoo.net/Zooref#bv97)) (and by similar arguments, is not in [P/poly](https://complexityzoo.net/Complexity_Zoo:P#ppoly)). > - BQP is not contained in [MA](https://complexityzoo.net/Complexity_Zoo:M#ma) ([Wat00](https://complexityzoo.net/Zooref#wat00)). > - BQP is not contained in [PH](https://complexityzoo.net/Complexity_Zoo:P#ph) ([RT18](https://complexityzoo.net/Zooref#rt18)) (see also [Wu18](https://complexityzoo.net/Zooref#wu18)). > - BQP is not contained in [ModpP](https://complexityzoo.net/Complexity_Zoo:M#modkp) for prime p ([GV02](https://complexityzoo.net/Zooref#gv02)). > - [NP](https://complexityzoo.net/Complexity_Zoo:N#np), and indeed [NP ∩ coNP](https://complexityzoo.net/Complexity_Zoo:N#npiconp), are not contained in BQP with probability 1 relative to a random oracle and a random permutation oracle, respectively ([BBB+97](https://complexityzoo.net/Zooref#bbb97)). > - [SZK](https://complexityzoo.net/Complexity_Zoo:S#szk) is not contained in BQP ([Aar02](https://complexityzoo.net/Zooref#aar02)). > - BQP is not contained in [SZK](https://complexityzoo.net/Complexity_Zoo:S#szk) (follows easily using the quantum walk problem in [CCD+03](https://complexityzoo.net/Zooref#ccd03)). > - BQP is not contained in [BPPpath](https://complexityzoo.net/Complexity_Zoo:B#bpppath "Complexity Zoo:B") ([Aar10](https://complexityzoo.net/Zooref#aar10)) (see also [Che16](https://complexityzoo.net/Zooref#che16)). > - [PPAD](https://complexityzoo.net/Complexity_Zoo:P#ppad) is not contained in BQP ([Li11](https://complexityzoo.net/Zooref#li11)). > - P=BQP and [PH](https://complexityzoo.net/Complexity_Zoo:P#ph) is infinite ([FR98](https://complexityzoo.net/Zooref#fr98)). > > If P=BQP relative to a random oracle then BQP=BPP ([FR98](https://complexityzoo.net/Zooref#fr98)).