In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error (in the sense that the algorithm is correct at least 2/3 of the time on all inputs).
Postselection is not considered to be a feature that a realistic computer (even a quantum one) would possess, but nevertheless postselecting machines are interesting from a theoretical perspective.
Removing either one of the two main features (quantumness, postselection) from PostBQP gives the following two complexity classes, both of which are subsets of PostBQP:
The addition of postselection seems to make quantum Turing machines much more powerful: Scott Aaronson proved[2] [3] PostBQP is equal to PP, a class which is believed to be relatively powerful, whereas BQP is not known even to contain the seemingly smaller class NP. Using similar techniques, Aaronson also proved that small changes to the laws of quantum computing would have significant effects. As specific examples, under either of the two following changes, the "new" version of BQP would equal PP:
|x\rangle
p | |
|\alpha | |
x| |
2 | |
|\alpha | |
x| |
In order to describe some of the properties of PostBQP we fix a formal way of describing quantum postselection. Define a quantum algorithm to be a family of quantum circuits (specifically, a uniform circuit family). We designate one qubit as the postselection qubit P and another as the output qubit Q. Then PostBQP is defined by postselecting upon the event that the postselection qubit is
|1\rangle
One can show that allowing a single postselection step at the end of the algorithm (as described above) or allowing intermediate postselection steps during the algorithm are equivalent.[4]
Here are three basic properties of PostBQP (which also hold for BQP via similar proofs):
(2/3)3+3(1/3)(2/3)2=20/27
L1\capL2
More generally, combinations of these ideas show that PostBQP is closed under union and BQP truth-table reductions.
Scott Aaronson showed[5] that the complexity classes (postselected bounded error quantum polynomial time) and PP (probabilistic polynomial time) are equal. The result was significant because this quantum computation reformulation of gave new insight and simpler proofs of properties of .
The usual definition of a circuit family is one with two outbit qubits P (postselection) and Q (output) with a single measurement of P and Q at the end such that the probability of measuring has nonzero probability, the conditional probability
Pr[''Q'' = 1|''P'' = 1] ≥ 2/3 if the input x is in the language, and Pr[''Q'' = 0|''P'' = 1] ≥ 2/3 if the input x is not in the language. For technical reasons we tweak the definition of as follows: we require that for some constant c depending on the circuit family. Note this choice does not affect the basic properties of, and also it can be shown that any computation consisting of typical gates (e.g. Hadamard, Toffoli) has this property whenever .Suppose we are given a family of circuits to decide a language L. We assume without loss of generality (e.g. see the inessential properties of quantum computers) that all gates have transition matrices that are represented with real numbers, at the expense of adding one more qubit.
Let denote the final quantum state of the circuit before the postselecting measurement is made. The overall goal of the proof is to construct a algorithm to decide L. More specifically it suffices to have L correctly compare the squared amplitude of in the states with to the squared amplitude of in the states with to determine which is bigger. The key insight is that the comparison of these amplitudes can be transformed into comparing the acceptance probability of a machine with 1/2.
Let n denote the input size, denote the total number of qubits in the circuit (inputs, ancillary, output and postselection qubits), and denote the total number of gates.Represent the ith gate by its transition matrix Ai (a real unitary
2B x 2B
|x\rangle
\Psi=AGAG-1...bA2A1|x\rangle
\pi1:=
Pr[P=1,Q=1]=\sum | |
\omega\inS1 |
2 | |
\Psi | |
\omega |
\pi0:=
Pr[P=1,Q=0]=\sum | |
\omega\inS0 |
2 | |
\Psi | |
\omega. |
The definition of ensures that either
\pi1\ge2\pi0
\pi0\ge2\pi1
Our machine will compare
\pi1
\pi0
\Psi\omega=
\sum | |
\alpha1,\ldots,\alphaG |
G | |
A | |
\omega,\alphaG |
G-1 | |
A | |
\alphaG,\alphaG-1 |
...b
2 | |
A | |
\alpha3,\alpha2 |
1 | |
A | |
\alpha2,\alpha1 |
x | |
\alpha1 |
where the sum is taken over all lists of G basis vectors
\alphai
\pi1
\pi0
\tfrac{1}{2}(1+\pi1-\pi0)
x\inL
\tfrac{1}{2}(1+\pi1-\pi0)>\tfrac12
x\not\inL
\tfrac{1}{2}(1+\pi1-\pi0)<\tfrac12
The definition of tells us that
\pi1\ge\tfrac{2}{3}(\pi0+\pi1)
\pi0\ge\tfrac{2}{3}(\pi0+\pi1)
2f(n)
\pi1>\tfrac{1}{2}(\pi0+\pi1)
\pi0>\tfrac{1}{2}(\pi0+\pi1)
(1+2-f(n)2B)G-1<
-nc | |
\tfrac{1}{6}2 |
,
Now we provide the detailed implementation of our machine. Let denote the sequence
\{\alphai\}
G | |
i=1 |
\Pi(A,\omega,\alpha,x):=
G | |
A | |
\omega,\alphaG |
G-1 | |
A | |
\alphaG,\alphaG-1 |
...b
2 | |
A | |
\alpha3,\alpha2 |
1 | |
A | |
\alpha2,\alpha1 |
x | |
\alpha1 |
\pi1-\pi0=
\sum | |
\omega\inS1 |
\sum\alpha,\alpha'\Pi(A,\omega,\alpha,x)\Pi(A,\omega,\alpha',x)-
\sum | |
\omega\inS0 |
\sum\alpha,\alpha'\Pi(A,\omega,\alpha,x)\Pi(A,\omega,\alpha',x).
\omega\not\inS0\cupS1
\alpha,\alpha'
X=\Pi(A,\omega,\alpha,x)\Pi(A,\omega,\alpha',x)
22f(n)G(n)
-1\leX\le1
\omega\inS1
\tfrac{1+X}{2}
\tfrac{1-X}{2}
\omega\inS0
\tfrac{1-X}{2}
\tfrac{1+X}{2}
1 | + | |
2 |
\pi1-\pi0 | |
21+B(n)+2B(n)G(n) |
,
Suppose we have a machine with time complexity on input x of length
n:=|x|
x\inL\Leftrightarrow\#\{r\in\{0,1\}T\midf(x,r)=1\}>2T-1
Define s to be the number of random strings which lead to acceptance,
s:=\#\{r\in\{0,1\}T\midf(x,r)=1\}
2T-s
s\not\in\{0,2T/2,2T\}
Aaronson's algorithm for solving this problem is as follows. For simplicity, we will write all quantum states as unnormalized. First, we prepare the state
|x\rangle ⊗
T} | |
\sum | |
r\in\{0,1\ |
|r\rangle|f(x,r)\rangle
|\psi\rangle:=(2T-s)|0\rangle+s|1\rangle.
H|\psi\rangle=(2T|0\rangle+(2T-2s)|1\rangle)/\sqrt{2}
\alpha,\beta
\alpha2+\beta2=1
\alpha|0\rangle|\psi\rangle+\beta|1\rangle|H\psi\rangle
\beta/\alpha
|\phi\beta/\alpha\rangle:=\alphas|0\rangle+
\beta | |
\sqrt{2 |
Visualizing the possible states of a qubit as a circle, we see that if
s>2T-1
x\inL
\phi\beta/\alpha
Qacc:=(-|1\rangle,|0\rangle)
s<2T-1
x\not\inL
\phi\beta/\alpha
Qrej:=(|0\rangle,|1\rangle)
\beta/\alpha
(0,infty)
|\phi\beta/\alpha\rangle
Let
|+\rangle=(|1\rangle+|0\rangle)/\sqrt{2}
Qrej
|-\rangle
|+\rangle
Qacc
\{|+\rangle,|-\rangle\}
|+\rangle
x\not\inL
\beta/\alpha=r*:=\sqrt{2}s/(2T-2s)
|\phi\beta/\alpha\rangle
\{|+\rangle,|-\rangle\}
|+\rangle
\beta/\alpha
Specifically, note
2-T<r*<2T
\beta/\alpha
2i
-T\leqi\leqT
|
\phi | |
2i |
\rangle
\{|+\rangle,|-\rangle\}
|+\rangle
(3+2\sqrt{2})/6 ≈ 0.971.
Overall, the algorithm is as follows. Let k be any constant strictly between 1/2 and
(3+2\sqrt{2})/6
-T\leqi\leqT
|
\phi | |
2i |
\rangle
\{|+\rangle,|-\rangle\}
ClogT
|+\rangle
Note that this algorithm satisfies the technical assumption that the overall postselection probability is not too small: each individual measurement of
|
\phi | |
2i |
\rangle
1/2O(T)
O(T2logT) | |
1/2 |