# I Does 'Phase Inversion' grow exponentially?

Tags:
1. Dec 13, 2017

### 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

2. Dec 13, 2017

### 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.

3. Dec 13, 2017

### Ricardo Belchior

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,

4. Dec 13, 2017

### 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.

5. Dec 13, 2017

### 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,

6. Dec 13, 2017

### 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.

7. Dec 14, 2017

### 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

#### Attached Files:

File size:
792 bytes
Views:
10
8. Dec 14, 2017

### 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.

9. Dec 14, 2017

### 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 cant be represented in single qubits?

Cheers

#### Attached Files:

File size:
352 bytes
Views:
9
10. Dec 14, 2017

### 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.

11. Dec 14, 2017

### Ricardo Belchior

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

12. Dec 14, 2017

### 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.