Does 'Phase Inversion' grow exponentially?

[Ricardo Belchior]

Hi!

So I'm studying Gover's Algorithm and I have this doubt:

Does 'Phase inversion gate' grows exponentially? I mean, if I want to signal the one combination that is the answer, I must be able to represent all 2^N states, where N is the number of qubits in the system. How do I do this without representing all states?

Cheers,
RB

 

[Strilanc]

You can do the phase inversion on $n$ qubits in $O(n)$ gates.

For example, suppose we want to negate the amplitude of the $|1111...111\rangle$ state, but not affect any other state's amplitude. In other words, we want to perform the operation "if q1 is ON and q2 is ON and q3 is ON and ... q[n-1] is ON then apply Z to q[n]". A simple way to do this efficiently is to use Toffoli gates ("if A and B are ON then toggle C") and ancilla qubits to gradually merge the conditions. For example, after you've applied the operation "if q1 and q2 then toggle a1", you can replace the q1 and q2 parts of the intended operation with a1. You keep merging controls like that until you're down to some constant-sized operation, then you do that constant-sized operation and uncompute all the Toffolis.

Looks like this:

Each Toffoli gate merges two controls into one, reducing the total number of controls by 1. There are n-1 controls, so it takes ~n-1 Toffoli gates to merge them all together. We're scaling linearly with the number of qubits.

On top of this simple construction, we can do tricks that reduce the depth of the circuit from O(n) to O(lg n) or we can do tricks that reduce the number of ancilla qubits from O(n) to O(1) or even 0.

 

[Ricardo Belchior]

Thanks for your reply.

But I have a question: How to "save" that, in this case, |11111> have some phase shift?

Lets see:

Am I thinking right? In the end, if you apply hadamard gate you'll get

|psi> = -|0> - |1> - |2> - ... - |2^5> and not

|psi> = |0> + |1> + |2> + ... - |2^5>

What am I doing wrong?

Cheers,

 

[Strilanc]

What do you mean by "saving" the phase shift? You don't have to do anything extra to save it, the circuit causes it to happen and that's that. It's not going to magically go away.

You seem to be confused about exactly what is being negated, and how the Toffoli gates affect where that negative sign is. I'm not exactly sure how to explain the right intuition... when you have classical gates mixed with phase gates (e.g. Toffolis and Zs), and removing the Z gates gives you an identity circuit, you just think in terms of which input states are hit by the phase.

You might find the blog post Proxy Phasing and Computed Phasing helpful. You might also find the circuit simulator Quirk useful for tracking where the negative signs are.

 

[Ricardo Belchior]

Thanks. I will read the post for sure.

That's the point. The toffoli negates the qubit but the phase goes with it. Just like in X case:

[0 1; 1 0]' * [a b]' = [b a]' , with a and b as complex numbers.

the numbers exchange with each other, and the phases too.

and if you get:

|psi> = |0> + |1> + |2> + ... - |2^5>

how to you go back to just 5 qubits? There is no combination ...

cheers,

 

[Strilanc]

The Toffoli gate doesn't negate the qubit, it conditionally toggles the qubit. This permutes which amplitude is assigned to which state. So you can think of it as re-arranging amplitudes without changing any. And what the circuit is doing is re-arranging the amplitudes into a layout where the target amplitude is all off on its own and easy to target without hitting the others, then the circuit undoes the re-arranging so that the amplitudes are back where they started but with the target negated.

 

[Ricardo Belchior]

Thanks again for your patience.

So the amplitude re-arrange that toffoli gate does is this right? :

If I change the phase of amplitude of |1> and apply again the toffoli gate I have:

Then, in the end, we have -|0>. Then I don't understand how do we get back to the input.

Cheers

 

[Strilanc]

What do you mean by "get back to the input"?

Also, that's a NOT gate not a Toffoli gate. Toffoli gates act on 3 qubits, i.e. groups of 8 amplitudes.

 

[Ricardo Belchior]

Thank you for your help. I think I figure it out ... I was looking wrong to the picture that you gave me earlier.

Ok now, how can we describe this single qubit operation with algebra since the qubits are entangled?

I.e how do I apply Z to:
[1 0 0 1]'

Given that Z is one qubit gate and that state can't be represented in single qubits?

Cheers

 

[Strilanc]

You use the tensor product to expand the operation so it applies to the whole state, i.e. you multiply the 4d state vector by $I \otimes Z$ (or $Z \otimes I$; depends which wire you put the Z on). In other words, group the state vector entries into pairs that differ on the target qubit but agree on all the other qubits, and apply the operation within each pair.

 

[Ricardo Belchior]

Ok but how I⊗Z look like? It should be a 4x4 matrix right?

 

[Strilanc]

Read the Wikipedia article on the Kronecker product (which is a specific kind of tensor product) and it will explain how to compute the matrix.