Does 'Phase Inversion' grow exponentially?

In summary: I'm too lazy to check).In summary, the conversation discusses the use of Gover's Algorithm and addresses a query about the exponential growth of the 'Phase inversion gate'. It is explained that this gate can be performed efficiently on a certain number of qubits using Toffoli gates and ancilla qubits. The circuit can also be optimized using various techniques. The conversation also clarifies the concept of "saving" phase shifts and provides helpful resources for better understanding the topic. Finally, the conversation touches on the algebraic representation of a single qubit operation on an entangled state.
  • #1
Ricardo Belchior
13
0
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
 
Physics news on Phys.org
  • #2
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:

big-ccz.png


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.
 

Attachments

  • big-ccz.png
    big-ccz.png
    2.7 KB · Views: 459
  • #3
Thanks for your reply.

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

Lets see:
upload_2017-12-13_19-28-57.png


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,
 

Attachments

  • upload_2017-12-13_19-28-57.png
    upload_2017-12-13_19-28-57.png
    3.3 KB · Views: 432
  • #4
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
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
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
Thanks again for your patience.

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

upload_2017-12-14_10-31-5.png


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

upload_2017-12-14_10-39-27.png


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

Cheers
 

Attachments

  • upload_2017-12-14_10-31-5.png
    upload_2017-12-14_10-31-5.png
    715 bytes · Views: 333
  • upload_2017-12-14_10-32-52.png
    upload_2017-12-14_10-32-52.png
    721 bytes · Views: 458
  • upload_2017-12-14_10-39-27.png
    upload_2017-12-14_10-39-27.png
    731 bytes · Views: 329
  • #8
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
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?

upload_2017-12-14_19-15-3.png
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
 

Attachments

  • upload_2017-12-14_14-27-13.png
    upload_2017-12-14_14-27-13.png
    299 bytes · Views: 461
  • upload_2017-12-14_19-15-3.png
    upload_2017-12-14_19-15-3.png
    2.4 KB · Views: 343
  • #10
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
Ok but how I⊗Z look like? It should be a 4x4 matrix right?
 
  • #12
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.
 

1. What is phase inversion?

Phase inversion is a phenomenon in which a system undergoes a change in its structure or properties due to external factors such as temperature, pressure, or composition. In the context of growth, phase inversion refers to the exponential increase in the growth rate of a system.

2. How does phase inversion affect growth?

Phase inversion can significantly impact the growth of a system by altering its structure or properties. In the case of exponential growth, phase inversion can lead to a sudden increase in the growth rate, resulting in rapid and often uncontrollable growth.

3. What factors contribute to phase inversion?

Several factors can contribute to phase inversion, including changes in temperature, pressure, and composition. Additionally, factors such as the presence of impurities or the formation of new phases can also trigger phase inversion.

4. Can phase inversion be controlled or prevented?

Yes, phase inversion can be controlled or prevented by carefully monitoring and controlling the external factors that can trigger it. This can be done through precise temperature and pressure control, as well as maintaining a stable composition of the system.

5. Are there any benefits to phase inversion in growth?

In some cases, phase inversion can lead to beneficial outcomes in growth, such as the formation of new and desired phases or the enhancement of certain properties. However, it is essential to control and monitor phase inversion to prevent any potential negative effects on the system.

Similar threads

  • Quantum Physics
Replies
22
Views
358
Replies
3
Views
754
  • Quantum Physics
Replies
8
Views
1K
Replies
16
Views
1K
Replies
2
Views
2K
Replies
4
Views
2K
Replies
8
Views
864
  • Quantum Physics
Replies
1
Views
726
  • Quantum Physics
Replies
2
Views
1K
Replies
2
Views
2K
Back
Top