BQP in PSPACE¶

Warning

This page below here is not yet finished/polished.

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\rangle\) - using only polynomial space.

An amplitude in Polynomial Space¶

To build this simulator, we will make the following changes: Get rid of the AddDuplicates function \(\leftarrow\) uses more RAM (kindof going backwards)

Change your Hadamard function:
Currently your Hadamard function Hadamard(input,wire) takes \(|i\rangle \rightarrow \frac{1}{\sqrt{2}}\left(|0\rangle + (-1)^i |1\rangle \right)\) Let’s make a new Hadamard function Hadamard(input,wire,s) which takes \(|i\rangle \rightarrow \frac{1}{\sqrt{2}}\left(|0\rangle + (-1)^i |1\rangle \right)\)

Measuring in Polynomial Time¶

Before you were probably applying MEASURE by using np.choice with the state vector. We obviously can’t do that here.

We are going to need to think more carefully about how to perform a MEASURE without having the whole vector.

We want to start by showing that if we get one element of the vector at a time, we can successfully perform a measure.

Grading

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

Hint: Choose a random number between 0 and 1 and then add up your amplitudes until the amplitudes exceed your random number.

# 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 

Now we need to figure out how to get a specific amplitude. Maybe the amplitude for the binary number \(|01101\rangle\). Once we’ve done this, then we can just loop over all the binary numbers and generate each of the amplitudes and use our MEASURE technique from above.

To do this, we shoudl think about our Simulator II. Remember we have three gates: H, CNOT, \(P(\theta)\). Two of these gates - CNOT and \(P(\theta)\) - don’t increase the amount of RAM That is being used at all. On the other hand, the Hadamard gate doubles the amount of RAM that is being used. Every binary number in your list, gets broken into two additional binary numbers.

We are going to modify simulator 2 in various ways.

Suppose you have a list of length \(l\) and apply the Hadamard to gate \(i\). After the application (before you combine duplicates), you are going to have a list of length \(2l\) with \(l\) binary numbers

Typically after the application of a gate, you would apply a AddDuplicates function. While this is important to decrease the total amount of RAM being used, we don’t have to do this to get a correct answer. This is because quantum mechanics is linear - i.e. if your list is [(a,'001'), (b,'010'), (c,'001')] or your list is [(a+c,'001'),(b,'010')] you will get the same answer at the end of the day. Convince yourself of this.

Grading

Now, run your code on the following circuit with and without the AddDuplicates function. Verify that it gives the same amplitude for every vector.

(circuit here)

This seems to be heading in the wrong direction. We saw two Hadamards where we could have potentially added some duplicates and we didn’t choose to leaving us using more RAM.

Let’s consider the list that’s produced immediately after the Hadamard acts on site \(i\). After the application of the Hadamard (before you combine duplicates), you then have \(l\) binary numbers with a 0 on site \(i\) and \(l\) binary numbers with a 1 on site \(i\). Let’s sort your list so that these two lists are separate.

Currently our simulators take as input simply the circuit (and the input state). Suppose we also take as input whether each Hadamard should leave either the “0” or “1” bit generate from each Hadamard. For example, we could run our circuit above as Simulator([1,0]). Then the first Hadamard should leave the “1” part of the list and the second Hadamard should be the “0” part of your list. We could do this by not using the AddDuplicate function and instead use the

def RemoveBit(i, s)

function which removes all the binary numbers with the i’th bit being s (either 0 or 1).

Notice that this simulator is not going to increase the RAM. After the RemoveBit each list is still the same length.

But now we are definitely going to get the wrong answer for our amplitude of \(|01101\rangle\). But suppose we run it four times returning

Simulator4([0,0])['01101']+Simulator4([0,1])['01101']+Simulator4([1,0])['01101']+Simulator4([1,1])['01101']

This will give you the amplitude of \(|01101\rangle\).

Grading

Write code that takes a circuit and gets the amplitude of \(|01101\rangle\). It’s going to have to look at the number of Hadamards and some over all of them. Verify that it gets the right answer for this amplitude using your simulator.

Show that you’re not using much RAM by printing out the average length of your list.

(circuit here)

Grading

Put it all together and write a code that succesfully does the MEASURE. The computational complexity is now exponential in the number of Hadamards which is painful.

It almost looks like you are working in constant space - your list never gets bigger. But you have to store which Hadamard bits you are going to use. This bit-string is linear in the number of Hadamards and the number of Hadamards could be polynomial in the number of qubits.

for j in range(0,12):
    print(j)

Computing in Physics (498CMP)

BQP in PSPACE

Contents

BQP in PSPACE¶

An amplitude in Polynomial Space¶

Measuring in Polynomial Time¶