BQP

complexity class

Uses your system voice; voice and rate in settings.

Q601325Snapshot

≈ 6 min read

Names in other languages

  • DeutschBQP
  • EnglishBQP
  • EspañolBQP
  • FrançaisBQP
  • עבריתBQP
  • ItalianoBQP
  • 日本語BQP
  • 한국어BQP

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

, RP, co-RP, BPP, PP), which generalise P within PSPACE. It is unknown if any of these containments are strict. 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.

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.

Definition

BQP can be viewed as the languages associated with certain bounded-error uniform families of quantum circuits. A language L is in BQP if and only if there exists a polynomial-time uniform family of quantum circuits \{Q_n\colon n \in \mathbb{N}\} , such that For all n \in \mathbb{N} , Q n takes n qubits as input and outputs 1 bit For all x in L, \mathrm{Pr}(Q_ (x)=1)\geq \tfrac{2}{3} For all x not in L, \mathrm{Pr}(Q_ (x)=0)\geq \tfrac{2}{3} 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. 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 −n c on the other hand, where c is any positive constant, and n is the length of input.

Suppose we have an algorithm that solves APPROX-QCIRCUIT-PROB, i.e., given a quantum circuit acting on qubits, and two numbers \alpha, \beta \in [0,1], \alpha > \beta , 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 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 of 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 of CNOT gates to flip the qubits. Then we can combine two circuits to get C' = Q_nC_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 always defer the measurement 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 circuit , 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. {{Math theorem|1=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_{m-1} \rightarrow |x\rangle)} \alpha_h .|name=Claim}} {{math proof|1=We have \alpha_x = \langle x|C|0\rangle ^{\otimes n} =\langle x |g_mg_{m-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_{m-1} \rightarrow |x\rangle) }} 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 any 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 all with the first qubit being , 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!

P and BQP

We know \mathsf{P} \subseteq \mathsf{BQP} , since every classical circuit can be simulated by a quantum circuit. 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) Discrete logarithm Simulation of quantum systems (see universal quantum simulator) Approximating the Jones polynomial at certain roots of unity Harrow-Hassidim-Lloyd (HHL) algorithm

See also

Hidden subgroup problem Polynomial hierarchy (PH) Quantum complexity theory QMA, the quantum equivalent to NP. QIP, the quantum equivalent to IP.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374423309 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

10 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.