Deutsch–Jozsa algorithm/Circuit Analysis

  • A
  • Thread starter bapgobears
  • Start date
  • Tags
    Analysis
In summary, the conversation discusses difficulties in understanding the analysis of the basic quantum circuit in Deutsch's Algorithm and the implications of having multiple qubits. It also touches on the concept of qubit representation, NOT and H gates, and the CNOT gate as an entangler/detangler. The conversation concludes with recommendations for additional resources on the fundamentals of quantum circuit analysis.
  • #1
bapgobears
3
0
I'm having a hard time following the analysis of the basic quantum circuit that illustrates Deutsch's Algorithm - essentially I'm not following the algebraic manipulations there making on the two input quantum bits (simple case). One analysis is given at the bottom of the page of the link I provided. I also can not follow the explanation given in section 1.4.3 of the excellent book Quantum Computation and Quantum Information by Michael Nielsen.

I think I understand the basic idea of a qubit and how it can be represented as a complex linear combination of two orthonormal basis states. I can see what a NOT gate does (swaps coefficients) and an H gate (create superpositions), and a CNOT gate although when you start using inputs that are a superposition of basis states I can get confused. For example, the bottom output of the Uf gate in the Duetsch algorithm is suppose to be y XOR f(x).

if y = (|0 - |1)/sqrt(2) and x is (|0 + |1)/sqrt(2) . How do you evaluate

((|0 - |1)/sqrt(2)) XOR f ((|0 + |1)/sqrt(2)) ??

What does it mean to do the XOR of two quantum bits in the general case? If they are computational basis, then that's similar to the classical case I think, but in the case above?

What makes it confusing is sometimes they just write 1 or 0 and not the Dirac notation |1> or |0>. Where they say f(0) - should that really be f(|0>)?

Also, when doing the analysis of multiple input gates they seem to write the states of the individual qubits right next to each other with no punctuation. I can't tell if they mean multiplication sometimes or not?

The funny thing is I more or less get the point they're making that in one measurement you can find out whether the f(x) is balanced or not - something that a classical computer can not do in one calculation, but I can't follow the logic on how they get they're final state.

Any insights, help, or suggestions would be really appreciated. Maybe you know of some good resources that go over more of the fundamentals of quantum circuit analysis?

Thanks,
Bretthttps://en.wikipedia.org/wiki/Deutsch–Jozsa_algorithm
 
Physics news on Phys.org
  • #2
It sounds like you haven't quite grasped the implications of the fact that, when you have ##n## 2-level quantum systems (i.e. qubits), the state of the system is a ##2^n##-level quantum system where each level corresponds to one of the ##2^n## values you can assign to ##n## bits.

The expression "((|0 - |1)/sqrt(2)) XOR f ((|0 + |1)/sqrt(2))" makes no sense. The XOR doesn't apply to two qubits and give a single qubit output. It applies inline to each of the components of the superposition, causing a re-arrangement. It works more like...

##\text{CNOT}_{2 \rightarrow 1} \cdot \left( \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle) \otimes \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle) \right)##

Combine the factors of ##\frac{1}{\sqrt{2}}##:

##= \text{CNOT}_{2 \rightarrow 1} \cdot \left( \frac{1}{2} (|0\rangle - |1\rangle) \otimes (|0\rangle + |1\rangle) \right)##

Distribute the tensor product over the subtraction:

##= \text{CNOT}_{2 \rightarrow 1} \cdot \left( \frac{1}{2} \left(|0\rangle\otimes \big(|0\rangle + |1\rangle\big) - |1\rangle\otimes \big(|0\rangle + |1\rangle\big) \right) \right)##

Distribute the tensor products over the additions:

##= \text{CNOT}_{2 \rightarrow 1} \cdot \left( \frac{1}{2} (|0\rangle\otimes |0\rangle + |0\rangle\otimes|1\rangle - |1\rangle\otimes |0\rangle - |1\rangle\otimes|1\rangle) \right)##

Use the equivalent-but-shorter notation ##|ab\rangle## instead of ##|a\rangle \otimes |b\rangle##:

##= \text{CNOT}_{2 \rightarrow 1} \cdot \left( \frac{1}{2} (|00\rangle + |01\rangle - |10\rangle - |11\rangle) \right)##

Distribute the CNOT:

##= \frac{1}{2} (\text{CNOT}_{2 \rightarrow 1} |00\rangle + \text{CNOT}_{2 \rightarrow 1} |01\rangle - \text{CNOT}_{2 \rightarrow 1} |10\rangle - \text{CNOT}_{2 \rightarrow 1} |11\rangle)##

Evaluate the CNOT against each ket (i.e. flip the first bit when the second bit is 1, so 11->01 but 10->10):

##= \frac{1}{2} (|00\rangle + |11\rangle - |10\rangle - |01\rangle)##

Re-order:

##= \frac{1}{2} (|00\rangle - |01\rangle - |10\rangle+ |11\rangle)##

Done.

We can confirm this by simulating in Quirk:

Screenshot from 2016-05-17 15:26:02.png


The output display shows a positive (rightward) amplitude for 00 and 11, and negative amplitude for 01 and 10. Just like we calculated. (The magnitudes also agree.)
 
Last edited:
  • #3
Oh my gosh, thank you Strilanc for putting me out of my misery. You put your finger on precisely my problem! I have not completely grasped the concept of how to work with multiple qubits - how they combine to from a 2^n level system. Your explanation helps a ton. I also found a youtube video just before I got to your post where the steps are explained in more detail, and the notation is a little more complete to help the beginner. I had no idea that a CNOT gate can be thought of as an entangler/detangler. I'm excited and now I can make more progress. That Quirk simulator is cool. Thank you so much! Brett

https://m.youtube.com/watch?v=6obTxeTSuNM
 
  • #5
Oh , yes, I will enjoy going through that series of videos, and by the author of the book I'm reading! Thanks again Strilanc!
 

Related to Deutsch–Jozsa algorithm/Circuit Analysis

1. What is the Deutsch-Jozsa algorithm?

The Deutsch-Jozsa algorithm is a quantum algorithm that determines whether a function, which takes in a string of bits as input, is constant or balanced. It was proposed by David Deutsch and Richard Jozsa in 1992 and is one of the earliest examples of a quantum algorithm that provides a speedup over classical algorithms.

2. How does the Deutsch-Jozsa algorithm work?

The Deutsch-Jozsa algorithm works by utilizing the principles of quantum superposition and interference. It uses a quantum circuit to perform a series of operations on the input bits, which eventually leads to a measurement that reveals whether the function is constant or balanced.

3. What is the significance of the Deutsch-Jozsa algorithm in quantum computing?

The Deutsch-Jozsa algorithm is significant because it was one of the first quantum algorithms to demonstrate a speedup over classical algorithms. This opened up the possibility of using quantum computers to solve problems faster and more efficiently than classical computers.

4. How is the Deutsch-Jozsa algorithm analyzed?

The Deutsch-Jozsa algorithm is analyzed using circuit analysis techniques, such as quantum gate decomposition and quantum gate count. These techniques help to understand the underlying operations of the algorithm and determine its efficiency and accuracy.

5. What are some potential applications of the Deutsch-Jozsa algorithm?

The Deutsch-Jozsa algorithm has potential applications in cryptography, data compression, and database search. It can also be used as a building block for more complex quantum algorithms.

Similar threads

  • Quantum Physics
Replies
1
Views
2K
  • Quantum Physics
2
Replies
39
Views
3K
Replies
16
Views
2K
  • Quantum Physics
Replies
1
Views
950
  • Quantum Physics
Replies
3
Views
907
  • Quantum Physics
Replies
1
Views
730
  • Quantum Physics
Replies
6
Views
2K
Replies
7
Views
944
  • Quantum Physics
Replies
11
Views
2K
  • Quantum Physics
Replies
8
Views
1K
Back
Top