PostBQP

Let n denote the input size, B = B(n) denote the total number of qubits in the circuit (inputs, ancillary, output and postselection qubits), and G = G(n) denote the total number of gates. Represent the ith gate by its transition matrix Aⁱ (a real unitary ${\displaystyle 2^{B}\times 2^{B}}$ matrix) and let the initial state be |x> (padded with zeroes). Then ${\displaystyle \Psi =A^{G}A^{G-1}\dotsb A^{2}A^{1}|x\rangle }$. Define S₁ (resp. S₀) to be the set of basis states corresponding to P = 1, Q = 1 (resp. P = 1, Q = 0) and define the probabilities

${\displaystyle \pi _{1}:={\text{Pr}}[P=1,Q=1]=\sum _{\omega \in S_{1}}\Psi _{\omega }^{2}}$

${\displaystyle \pi _{0}:={\text{Pr}}[P=1,Q=0]=\sum _{\omega \in S_{0}}\Psi _{\omega }^{2}.}$

The definition of PostBQP ensures that either ${\displaystyle \pi _{1}\geq 2\pi _{0}}$ or ${\displaystyle \pi _{0}\geq 2\pi _{1}}$ according to whether x is in L or not.

Our PP machine will compare ${\displaystyle \pi _{1}}$ and ${\displaystyle \pi _{0}}$. In order to do this, we expand the definition of matrix multiplication:

${\displaystyle \Psi _{\omega }=\sum _{\alpha _{1},\ldots ,\alpha _{G}}A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}}$

where the sum is taken over all lists of G basis vectors ${\displaystyle \alpha _{i}}$. Now ${\displaystyle \pi _{1}}$ and ${\displaystyle \pi _{0}}$ can be expressed as a sum of pairwise products of these terms. Intuitively, we want to design a machine whose acceptance probability is something like ${\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})}$, since then ${\displaystyle x\in L}$ would imply that the acceptance probability is ${\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})>{\tfrac {1}{2}}}$, while ${\displaystyle x\not \in L}$ would imply that the acceptance probability is ${\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})<{\tfrac {1}{2}}}$.

The definition of PostBQP tells us that ${\displaystyle \pi _{1}\geq {\tfrac {2}{3}}(\pi _{0}+\pi _{1})}$ if x is in L, and that otherwise ${\displaystyle \pi _{0}\geq {\tfrac {2}{3}}(\pi _{0}+\pi _{1})}$. Let us replace all entries of A by the nearest fraction with denominator ${\displaystyle 2^{f(n)}}$ for a large polynomial ${\displaystyle f(n)}$ that we presently describe. What will be used later is that the new π values satisfy ${\displaystyle \pi _{1}>{\tfrac {1}{2}}(\pi _{0}+\pi _{1})}$ if x is in L, and ${\displaystyle \pi _{0}>{\tfrac {1}{2}}(\pi _{0}+\pi _{1})}$ if x is not in L. Using the earlier technical assumption and by analyzing how the 1-norm of the computational state changes, this is seen to be satisfied if ${\displaystyle (1+2^{-f(n)}2^{B})^{G}-1<{\tfrac {1}{6}}2^{-n^{c}},}$ thus clearly there is a large enough f that is polynomial in n.

Now we provide the detailed implementation of our PP machine. Let α denote the sequence ${\displaystyle \{\alpha _{i}\}_{i=1}^{G}}$ and define the shorthand notation

${\displaystyle \Pi (A,\omega ,\alpha ,x):=A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}}$,

then

${\displaystyle \pi _{1}-\pi _{0}=\sum _{\omega \in S_{1}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)-\sum _{\omega \in S_{0}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x).}$

We define our PP machine to

• pick a basis state ω uniformly at random
• if ${\displaystyle \omega \not \in S_{0}\cup S_{1}}$ then STOP and accept with probability 1/2, reject with probability 1/2
• pick two sequences ${\displaystyle \alpha ,\alpha '}$ of G basis states uniformly at random
• compute ${\displaystyle X=\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)}$ (which is a fraction with denominator ${\displaystyle 2^{2f(n)G(n)}}$ such that ${\displaystyle -1\leq X\leq 1}$)
• if ${\displaystyle \omega \in S_{1}}$ then accept with probability ${\displaystyle {\tfrac {1+X}{2}}}$ and reject with probability ${\displaystyle {\tfrac {1-X}{2}}}$ (which takes at most ${\displaystyle 2f(n)G(n)+1}$ coin flips)
• otherwise (then ${\displaystyle \omega \in S_{0}}$) accept with probability ${\displaystyle {\tfrac {1-X}{2}}}$ and reject with probability ${\displaystyle {\tfrac {1+X}{2}}}$ (which again takes at most ${\displaystyle 2f(n)G(n)+1}$ coin flips)

Then it is straightforward to compute that this machine accepts with probability ${\displaystyle {\frac {1}{2}}+{\frac {\pi _{1}-\pi _{0}}{2^{1+B(n)+2B(n)G(n)}}},}$ so this is a PP machine for the language L, as needed.

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 ${\displaystyle \sum _{x\in \{0,1\}^{T}}|x\rangle |f(x)\rangle }$. Second, we apply Hadamard gates to the first register (each of the first T qubits), measure the first register and postselect on it being the all-zero string. It is easy to verify that this leaves the last register (the last qubit) in the residual state

${\displaystyle |\psi \rangle$ :=(2^{T}-s)|0\rangle +s|1\rangle .}

Where H denotes the Hadamard gate, we compute the state

${\displaystyle H|\psi \rangle =(2^{T}|0\rangle +(2^{T}-2s)|1\rangle )/{\sqrt {2}}}$.

Where ${\displaystyle \alpha ,\beta }$ are positive real numbers to be chosen later with ${\displaystyle \alpha ^{2}+\beta ^{2}=1}$, we compute the state ${\displaystyle \alpha |0\rangle |\psi \rangle +\beta |1\rangle |H\psi \rangle }$ and measure the second qubit, postselecting on its value being equal to 1, which leaves the first qubit in a residual state depending on ${\displaystyle \beta /\alpha }$ which we denote

${\displaystyle |\phi _{\beta /\alpha }\rangle$ :=\alpha s|0\rangle +{\frac {\beta }{\sqrt {2}}}(2^{T}-2s)|1\rangle } .

Visualizing the possible states of a qubit as a circle, we see that if ${\displaystyle s>2^{T-1}}$, (i.e. if ${\displaystyle x\in L}$) then ${\displaystyle \phi _{\beta /\alpha }}$ lies in the open quadrant ${\displaystyle Q_{acc}:=(-|1\rangle ,|0\rangle )}$ while if ${\displaystyle s<2^{T-1}}$, (i.e. if ${\displaystyle x\not \in L}$) then ${\displaystyle \phi _{\beta /\alpha }}$ lies in the open quadrant ${\displaystyle Q_{rej}:=(|0\rangle ,|1\rangle )}$. In fact for any fixed x (and its corresponding s), as we vary the ratio ${\displaystyle \beta /\alpha }$ in ${\displaystyle (0,\infty )}$, note that the image of ${\displaystyle |\phi _{\beta /\alpha }\rangle }$ is precisely the corresponding open quadrant. In the rest of the proof, we make precise the idea that we can distinguish between these two quadrants.

Let ${\displaystyle |+\rangle =(|1\rangle +|0\rangle )/{\sqrt {2}}}$, which is the center of ${\displaystyle Q_{rej}}$, and let ${\displaystyle |-\rangle }$ be orthogonal to ${\displaystyle |+\rangle }$. Any qubit in ${\displaystyle Q_{acc}}$, when measured in the basis ${\displaystyle \{|+\rangle ,|-\rangle \}}$, gives the value ${\displaystyle |+\rangle }$ less than 1/2 of the time. On the other hand, if ${\displaystyle x\not \in L}$ and we had picked ${\displaystyle \beta /\alpha =r^{*}:={\sqrt {2}}s/(2^{T}-2s)}$ then measuring ${\displaystyle |\phi _{\beta /\alpha }\rangle }$ in the basis ${\displaystyle \{|+\rangle ,|-\rangle \}}$ would give the value ${\displaystyle |+\rangle }$ all of the time. Since we don't know s we also don't know the precise value of r*, but we can try several (polynomially many) different values for ${\displaystyle \beta /\alpha }$ in hopes of getting one that is "near" r*.

Specifically, note ${\displaystyle 2^{-T}<r*<2^{T}}$ and let us successively set ${\displaystyle \beta /\alpha }$ to every value of the form ${\displaystyle 2^{i}}$ for ${\displaystyle -T\leq i\leq T}$. Then elementary calculations show that for one of these values of i, the probability that the measurement of ${\displaystyle |\phi _{2^{i}}\rangle }$ in the basis ${\displaystyle \{|+\rangle ,|-\rangle \}}$ yields ${\displaystyle |+\rangle }$ is at least ${\displaystyle (3+2{\sqrt {2}})/6\approx 0.971.}$

Overall, the PostBQP algorithm is as follows. Let k be any constant strictly between 1/2 and ${\displaystyle (3+2{\sqrt {2}})/6}$. We do the following experiment for each ${\displaystyle -T\leq i\leq T}$: construct and measure ${\displaystyle |\phi _{2^{i}}\rangle }$ in the basis ${\displaystyle \{|+\rangle ,|-\rangle \}}$ a total of ${\displaystyle C\log T}$ times where C is a constant. If the proportion of ${\displaystyle |+\rangle }$ measurements is greater than k, then reject. If we don't reject for any i, accept. Chernoff bounds then show that for a sufficiently large universal constant C, we correctly classify x with probability at least 2/3.

Note that this algorithm satisfies the technical assumption that the overall postselection probability is not too small: each individual measurement of ${\displaystyle |\phi _{2^{i}}\rangle }$ has postselection probability ${\displaystyle 1/2^{O(T)}}$ and so the overall probability is ${\displaystyle 1/2^{O(T^{2}\log T)}}$.