Deutch-Jozsa Algorithm Explained

SCIENCES 6 SNI LICENCE 3 SCIENCES POUR L’INGÉNIEUR TOOLS BOX 1.Python Notebook updates 2.KAIST video class 3.Kindle e-books & paper editions 4.Textbook SpinQ Gemini & Mini 5.Interface Spin Quasar (expérience on 2 qbits & simulation on 8 qbits) TOOLS BOX 6.Quantum computers on...

SCIENCES 6 SNI LICENCE 3 SCIENCES POUR L’INGÉNIEUR TOOLS BOX 1.Python Notebook updates 2.KAIST video class 3.Kindle e-books & paper editions 4.Textbook SpinQ Gemini & Mini 5.Interface Spin Quasar (expérience on 2 qbits & simulation on 8 qbits) TOOLS BOX 6.Quantum computers online 7.IQM Academy 8.PowerPoint Moodle 9.Exercises Moodle 10 Research papers OVERVIEW DEUTSH - JOZSA ALGORITHM Problem statement Classical solution Quantum solution  Problem Statement Boolean function CONSTANT Takes n bits to 1 bits f(x) = c for all x Example : N=2 BALANCED CONSTANT BALANCED f(x)=0 for exaltly half of the possible input f(00) =0 0 f(00) = And f(x)=0 for other f(01) =0 f(01) =1 f(10) =0 f(10) =0 f(11) =0 f(11) =1 What is f ?  CLASSICAL SOLUTION BEST CASE We need 2 queries of the function f Þ First query gives the output 0 Þ Second query gives the outpout f will be BALANCE 1  CLASSICAL SOLUTION WORST CASE We need queries of the function f Example Input x N=3 Output f(x) 000 0 001 0 queries 010 0 Queries are need to 0 : f is CONSTANT 011 0 1 : f is BALANCE be 100% certain !! 100 101 110 111  QUANTUM SOLUTION Only 1 query of the function f is need ! Implement f as the quantum oracle the maps |x>|y> |x>|y ⊕ f(x) > Of QUANTUM SOLUTION |ᴪ0> = |0 ⊕N > ⓧ |1> |ᴪ1> = H ⊕N |0 ⊕N > ⓧ |1> side step of Hadamard Transfom QUANTUM SOLUTION Hadamard Transform For N=2 ⓧ = ⓧ 2 bit string QUANTUM SOLUTION Oracle  QUANTUM SOLUTION 𝑁 2 −1 1 1 |𝜑 ⟩ = ∑ |𝑥 ⟩ ⓧ (| 𝑓 ( 𝑥 ) ⟩ −|1 ⊕ 𝑓 ( 𝑥 ) ⟩ ) 2 √2 𝑁 2 𝑥=0 2 si f(x)=0 = si f(x)=1 𝑁 = 2 −1 1 1 |𝜑 2 ⟩ = ∑ | 𝑥 ⟩ ⓧ ( − 1 ) 𝑓 (𝑥) (|0 ⟩ −|1 ⟩ ) √2 𝑁2 𝑥=0 2  QUANTUM SOLUTION Hadamard to each qbit in first register of first register QUANTUM SOLUTION [ ] 𝑁 2 −1 1 1 |𝜑 3 ⟩=𝐻 ∑ |𝑥 ⟩ (|0 ⟩ −| 1 ⟩ ) ⓧN 𝑓 (𝑥) ( − 1) ⓧ 𝑁 2 𝑥=0 √2 2 [ ] 𝑁 𝑁 2 −1 2 −1 1 1 |𝜑 3 ⟩= 𝑁 ∑ ∑ ( − 1) 𝑓 (𝑥 ) ( − 1) 𝑥⊙𝑦 | 𝑦 ⟩ ⓧ (| 0 ⟩ −|1 ⟩ ) 2 𝑦=0 𝑥=0 √2  QUANTUM SOLUTION Measure first register Probability to obtain  QUANTUM SOLUTION If f is constant = If f is balanced = Half of time Half of time Thus, if we measure the outcome Any other measurement result means that f(x) is BALANCED  QUANTUM SOLUTION To determine with 100% certainly if the oracle function is CONSTANT or BALANCED : Classical solution queries queries Quantum solution queries only 1 query EXPONETIAL SPEED-UP !!!