BQP in PSPACE

Extra Credit

Everything on this page is extra credit worth 20 points.

In this section, we are going to build Simulator 4. Our previous simulators were exponential in both time and space (RAM). This simulator is going to be special because it is going to be (at least) exponential in time but it’s going to require only a polynomial amount of space. In fact, it uses so little space that you’d be able to run very large calculations on your laptop as long as you’d be willing to wait a really long time for your result.

The class which can be solved with polynomial amount of space but arbitrary computation (i.e. your laptop with the same RAM but really really fast clock speed) is class PSPACE.

By building simulator 4 (and showing that it works in polynomial space) you will have demonstrated that BQP in PSPACE.

We need to start by taking some care with what we mean by running a quantum computation. Previously, we’ve allowed our simulator to output the state vector (something a real quantum computer can’t do but we could). But the state vector is already exponentially large so we can’t even print it out in polynomial time. Instead, we will require this simulator to only work when MEASURE is applied.

We will worry about figuring out how to implement the measure later. Let’s start by figuring out how to evaluate one amplitude - i.e. what’s the amplitude of $|101⟩$ - using only polynomial space.

An amplitude in Polynomial Space

First notice that in Simulation II, the thing that is cost you RAM is that you are doubling your list length every time you do a Hadamard. Nothing but the Hadamard is causing trouble.

To build this simulator, we will make the following changes. Get rid of the AddDuplicates function in simulator II. Notice that this uses more RAM so seems to be going backwards.

Grading

Go ahead and implement this code. Verify that you still get the same answer that you previously did (i.e. the add duplicates function was an efficiency improvement but not important).

Currently, we are using a lot of RAM. Now we are going to make a change to our simulation. Our simulation (which we will use as a subroutine for a bigger simulation) is going to take (1) a quantum circuit (which has $k$ Hadamards in it and (2) a binary number of length $k$. For example, if we had four Hadamards, our simulator might take the number $1011$. We will interpret this as only taking the “1” path of the first Hadamard, the “0” path of the second Hadamard, the “1” path of the third Hadamard and the “1” path of the fourth Hadamard.

Recall that your Hadamard function Hadamard(input,wire) takes $|i⟩\to \frac{1}{\sqrt{2}}(|0⟩+(-1{)}^i|1⟩)$

Grading

Make a new Hadamard function Hadamard(input,wire,s) which takes $|i⟩\to \frac{1}{\sqrt{2}}(|0⟩+(-1{)}^i|1⟩)$ and the bit s and returns the correct result.

Notice that when you run this new simulation it gives the wrong answer, but it doesn’t take very much RAM at all. The only place you were previously consuming RAM was that your Hadamard gate was doubling the list length each time. Now it’s not.

---

Putting it together

Currently we are using less RAM but getting the wrong answer. Now, we want to go ahead and change things so we can get the correct answer and still not use much RAM. Let’s say we are trying to figure out the amplitude for $|101⟩$. Let’s run our new simulation using all possible binary numbers (for the choices for our Hadamard). Each one of those simulations is going to give us a value for the amplitude. We should sum them all. This is going to require an exponential number, $2^k$, runs of our simulation but each one takes very little RAM (we will count carefully in a minute).

We now have an algorithm which gives us the amplitude for a particular binary number.

Grading

Go ahead and implement in your code. Run a circuit of four Hadamards and compute the amplitude for $|101⟩$. Check that you get the same result for that amplitude using Simulator II.

Measuring in Polynomial Time

We now are able to get a particular amplitude in polynomial time. As the next step, we’d like to be able to implement the MEASURE function.

Before you were probably applying MEASURE by using np.choice with the state vector. We obviously can’t do that here since we can’t afford to write out the state vector. We are going to need to think more carefully about how to perform a MEASURE without having the whole vector.

Essentially, we are going to invert things. Let’s first choose a random number $r\in (0,1)$. Then we are just going to enumerate over the different binary numbers $|i⟩$ computing the amplitude (and then the probability) for each one. We can then subtract off the probability from our random number until we find the amplitude that makes it zero (be careful here about off-by-one errors).

Grading

Write code to successfully perform measure where you see one amplitude at a time.

# do something (probably including pick a random number)
for amp in stateVector:
    # you can do whatever you want here 
    # except for store a lot of these amplitudes
    # return something 

---