I found the following proof of BQP belonging to PP (the original document is here). There is a part of the proof that I have trouble understanding. First, the structure is given below.

We try to simulate a polynomial-time generated quantum circuit (which encodes our problem) using a PP machine. We start with a universal set of gates.

We have a Hadamard gate and a Toffoli gate. We also include a $i$-phase shift gate ($|0 \rangle$ $\rightarrow |0 \rangle, |1 \rangle \rightarrow i|1 \rangle$). However, we simulate the action of this gate by considering an additional qubit and performing the following transformations:

$$|00 \rangle → |00 \rangle $$ $$|01 \rangle → |01 \rangle $$ $$|10\rangle→ |11 \rangle $$ $$|11 \rangle → −|10 \rangle $$

The first qubit is viewed as the original qubit and the additional qubit acts as the "real/imaginary part".

There is a register $B \leftarrow 0$ to store the phase. A register $Z$ $\leftarrow 0^n$ stores the initial state of the machine. We simulate the circuit as follows:

$\bullet$ If the gate is a Toffoli gate, simply modify $Z$ accordingly.

$\bullet$ If the gate is a Hadamard gate, flip a coin to determine the new state of the corresponding bit of $Z$. If the induced transformation was $1 \rightarrow 1$, toggle the sign bit.

$\bullet$ If the gate is the two-qubit gate we used to replace the $i$-phase shift gate, modify $Z$ appropriately and toggle the sign bit if the transformation induced was $11 \rightarrow 10$.

The steps above are repeated a second time, using variables $B'$ and $Z'$ in place of $B$ and $Z$. Finally, the following operations are performed:

$\bullet$ If $Z = Z'$ and the first bit of $Z$ and $Z'$ is a $0$, then output $B ⊕ B'$.

$\bullet$ If $Z = Z'$ and the first bit of $Z$ and $Z'$ is a $1$, then output $\bar B ⊕ B'$.

$\bullet$ If $Z \neq Z'$, then “give up”. This means: flip a fair coin and output $0$ or $1$ accordingly.

The claim is that the algorithm above simulates a BQP circuit on a PP machine faithfully as the probability the algorithm outputs $1$ minus the probability that the algorithm outputs $0$ is proportional to $\langle 1 | Q_x |1 \rangle - \langle 0 | Q_x |0 \rangle$ (where $Q_x$ is the quantum circuit for a given encoding $x$ from a polynomial-time generated uniform family of quantum circuits). I do not understand why the terms are proportional.


1 Answer 1


Two quick comments before explaining this:

  1. The notes don't actually contain a proof of the claim made about the simulation; the intention was only to give a basic idea of how the simulation works. It is therefore not at all surprising that the mathematical justification is not clear, because the notes didn't even try to explain it. (It was the last lecture of the course and there just wasn't time to go over it in detail.)

  2. The notation is a little bit unusual here: we're interpreting $Q_x$ as the one-qubit mixed state output by the circuit corresponding to $x$, so $\langle 1 | Q_x | 1 \rangle$ is the probability that $Q_x$ outputs 1 and $\langle 0 | Q_x | 0 \rangle$ is the probability that $Q_x$ outputs 0. The point is that we want the probability that our algorithm outputs 1 minus the probability it outputs 0 to be proportional to the probability the circuit outputs 1 minus the probability it outputs zero.

Moving on to the actual question, let us suppose that $x$ is fixed so that we can just talk about a single quantum circuit $Q$ that acts on $n$ qubits and has $t$ gates of the type described in the question: Hadamard gates, Toffoli gates, and these two-qubit gates that mimic phase shift gates. (You can ignore these if you want, so long as you accept that Toffoli and Hadamard gates are universal for quantum computation. The point is that we do not want to deal with non-real numbers.)

Now, consider a sequence of binary strings $(y_0,\ldots,y_t)$, where each of these strings has length $n$ and there are $t+1$ strings in total. We can think of such a sequence as a possible computation path through the circuit, where $y_0$ represents a classical state of $n$ qubits at time 0, $y_1$ represents a classical state of $n$ qubits at time 1, and so on. Let us call such a path valid if $y_0 = 0^n$ and, for every choice of $k\in\{1,\ldots,t\}$, the $k$-th gate of $Q$ takes $|y_{k-1}\rangle$ to $|y_k\rangle$ with a nonzero amplitude. (Given our limited choice of gates, this nonzero amplitude will always be $\pm 1$ or $\pm 1/\sqrt{2}$.)

Associated with any such path $P = (y_0,\ldots,y_t)$ is an amplitude $\alpha(P)$. Given the gates we are considering, the amplitude $\alpha(P)$ for each valid path $P$ will always take the form $$ \alpha(P) = \frac{s(P)}{2^{m/2}} $$ where $s(P)\in\{-1,+1\}$ and $m$ is the total number of Hadamard gates in the circuit. The probability that the circuit outputs a string $z\in\{0,1\}^n$ is equal to $$ \left(\sum_P \alpha(P)\right)^2 = \frac{1}{2^m} \sum_P \sum_Q s(P) s(Q), $$ where in these sums $P$ and $Q$ range only over the valid paths that end at $z$.

Now consider the probabilistic algorithm. We can again consider paths of the same form as before: $P = (y_0,\ldots,y_t)$. This time, think of these strings as the sequences of states of the register $Z$. The probability associated with each valid path $P$ will be $2^m$, and the bit $B$ will always track the sign of the corresponding amplitude, so that after running through all of the gates you will have $B = 0$ if $s(P) = +1$ and $B = 1$ if $s(P) = -1$. The same reasoning is applied, independently, to $Z'$ and $B'$ for the second run through the process.

Now, for a particular choice of a final string $z\in\{0,1\}^n$, consider the situation in which both paths $P$ and $P'$ end in $z$, and look at the binary value $B\oplus B'$. This value is 0 if $B$ and $B'$ are equal, which is the same as saying $s(P)s(Q) = +1$, and 1 if $B$ and $B'$ are different, which is the same as saying $s(P)s(Q) = -1$. Therefore, if the final string contained in $Z$ and $Z'$ is $z$, then the probability that the algorithm outputs 0 minus the probability that it outputs 1 is $$ \frac{1}{2^{2m}} \sum_P \sum_Q s(P) s(Q), $$ where again we're restricting the sums to valid paths $P$ and $Q$ that end at $z$.

If the final strings of $Z$ and $Z'$ are different, the algorithm just outputs a random bit, so the probability of outputting 0 minus the probability it outputs 1 is zero, so there's effectively no contribution to the bias of the output in this case.

Finally, consider the probabilities as we range over all possible final strings $z$. For those strings beginning with 0, which represent the quantum circuit outputting 0, the expression above is the probability that the algorithm outputs 0 minus the probability it outputs 1. For choices of $z$ beginning with 1, which corresponds to the quantum circuit outputting 1, the algorithm flips the output ($1\oplus B \oplus B'$ would have been a better way to write it than $\overline{B}\oplus B'$). Summing everything up, the probability that the algorithm outputs 1 minus the probability it outputs 0 is exactly $2^{-m}$ times the probability that the quantum circuit outputs 1 minus the probability if outputs zero.

This argument is based on the original proof of $\text{BQP}\subseteq\text{PP}$ found in this paper:

Adleman, DeMarrais, and Huang. Quantum Computability. SIAM Journal on Computing 26(5): 1524-1540, 1997.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.