Quantum algorithms covering evolution, DJ, Shor's and Grover's algorithms

This slide is featured in my video (https://youtu.be/CJ74J__1wmM) on quantum algorithms. It presents the evolution of quantum algorithms and offers an in-depth explanation of three significant quantum algorithms: the Deutsch-Jozsa (DJ) algorithm, Shor’s algorithm, and Grover’s algorithm.

1. Quantum Algorithms Kathiresan S

2. 2 Agenda Quantum Algorithms Introduction Evolution of algorithms Deutch-Jozsa algorithm Shor’s algorithm Grover’s Algorithm

3. 3 Introduction A quantum algorithm is a step-by-step procedure that runs on a quantum computer to solve a computational problem by using the principles of quantum mechanics such as: Superposition (Enables parallel exploration of many possibilities) Entanglement (Correlates qubit states in complex ways) Interference (Cancels wrong answers, amplifies correct ones) Why Do We Need Quantum Algorithms? Solving certain problems are too hard or slow for classical computers (e.g., factoring large numbers, simulating molecules). Unlike classical computers, where performance is often tied to processor speed , it’s the clever design of quantum algorithms that unlocks the true power of quantum computing They're foundational to quantum computing’s future impact in cryptography, chemistry, AI, and optimization, etc.

4. 4 Evolution of QC Algorithms From Theory to Application 1985 — Deutsch's Algorithm: Demonstrated a problem quantum computers can solve faster than classical ones. 1992 — Deutsch–Jozsa Algorithm: Determine whether a function is constant or balanced. 1994 — Shor’s Algorithm: Factor large integers efficiently. 1996 — Grover’s Algorithm: Search an unsorted database. Mathematical and Simulation-Oriented Algorithms Quantum Fourier Transform (QFT) - Core of many algorithms like Shor’s. Quantum Walk Algorithms - Quantum analogues of random walks. Harrow–Hassidim–Lloyd (HHL) Algorithm (2009) - Solve systems of linear equations. Hybrid and Variational Algorithms (2014–Present) VQE (Variational Quantum Eigensolver ) - Approximate ground state energies of molecules. QAOA (Quantum Approximate Optimization Algorithm) - Solve combinatorial optimization problems (e.g., MaxCut ) Quantum Machine Learning (QML) - Algorithms like Quantum SVM and QNNs Quantum Amplitude Estimation (QAE) - Quantum version of Monte Carlo

5. 5 Phase Kickback Kickback examples https://towardsdatascience.com/quantum-phase-kickback-bb83d976a448#:~:text=So%2C%20the%20CNOT%2Dgate%20does,call%20this%20phenomenon%20phase%20kickback.

6. 6 Deutsch- Jozsa Algorithm Problem We are given a hidden Boolean function f , which takes as input a string of bits, and returns either 0 or 1 for every input, that is: f:{0,1} n → {0,1} The property of the given Boolean function is that it is guaranteed to either be constant or balanced . A constant function returns all 0s or all 1s for any input, while a balanced function returns 0s for half of all inputs and 1s for the other half. We need to find out whether the function is constant or balanced Quantum advantage Minimum of 2 and a maximum of queries/ invocations are required to get a probability of success = 1 in classical approach 1 q uery is sufficient to get the right answer in quantum approach  

7. 7 Deutsch- Jozsa Algorithm ...contd. Oracle Inputs/ data Ancilla/ target =           For a two-qubit state, This is a uniform superposition of all n -bit strings on the data register, tensored with the ancilla in |−⟩ = (|0⟩ - |1⟩)/√2 state

8. 8 Oracle   Deutsch- Jozsa Algorithm ...contd.         =    

9. 9 Deutsch- Jozsa Algorithm ...contd.     Applying H ⊗n to the data register: Applying to every superposition of previous states: Substituting the Hadamard action,

10. 10 What does this mean for 2-qubit (data) system? H ⊗2 means applying Hadamard to both qubits . ∣x⟩ is one of the four basis states: ∣00⟩, ∣01⟩, ∣10⟩, or ∣11⟩. The sum is over all z ∈ {00,01,10,11} The exponent x⋅z is the bitwise dot product modulo 2 .   Deutsch- Jozsa Algorithm ...contd. x f(x) z x·z f(x) + x·z (–1) f(x)+x·z 00 00 +1 01 00 [phone] Balanced, Assume f(x)=0 for x=00,01 and f(x)=1 for x=10,11 for z = 00 x f(x) z x·z f(x) + x·z (–1) f(x)+x·z 00 1 00 1 -1 01 1 00 1 -1 10 1 00 1 -1 11 1 00 1 -1 Constant f(x) = 1 for all x and for z = 00

11. 11 Oracle Deutsch- Jozsa Algorithm ...contd.      

12. 12 DJ algorithm - Hands-on

13. 13 Shor’s algorithm This is to find prime factors of an integer and invented by an American mathematician Peter Shor in 1994 Classically, factoring large numbers takes exponential time. Shor's algorithm runs in polynomial time using quantum Fourier transform Could be used to break RSA cryptography schemes (used in online transactions) This is much faster than the most efficient known classical factoring algorithm. ( eg. To break RSA 2048 which will use a 617-digit number, it will take many years in classical computer and a few minutes in a perfect Quantum Computer)

14. 14 Factoring Algorithm - Number Theory N = P.Q where N is an odd composite number and P & Q are odd prime numbers (of roughly equal in length/ value) : N divides ( ) or (X - 1)(X + 1) but not X - 1 and X + 1 GCD (N, X -1) and GCD(N, X + 1) will give factors of N  

15. 15 Shor’s quantum factoring algorithm steps Classical Preprocessing Get the number N to be factored Pick a random integer 𝑎, 1 < 𝑎 < 𝑁-1, Compute 𝑔 = gcd⁡(𝑎,𝑁) & If 𝑔 > 1, you’ve already found a nontrivial factor Quantum Period‐Finding Find out the period r such that a r = 1(mod N) using QPE Arrive at the Unitary matrix U ( U:∣y⟩↦∣ay mod N⟩ ) Generate QPE circuit using counting registers, work registers, apply controlled modular exponentiation Add inverse QFT module Measure the counting register ( m bit outcome k & k/2 m ≈ s/r) Classical Postprocessing Use the continued‐fraction algorithm on 𝑘/2 𝑚 to recover the denominator 𝑟 Check that 𝑟 is even and 𝑎 𝑟/2 ≠ −1(mod 𝑁) Compute gcd (𝑎 𝑟/2 ±1, 𝑁) → nontrivial factors of 𝑁 If any check fails, pick a new 𝑎 and repeat Probability of guessing Probability of guessing the right a is where k is the number of distinct odd prime factors of N  

16. 16 Understanding the period ‘r’ What is period r? The period or order (r), is the smallest (non-zero) integer such that x r mod N = 1 Let us assume N = 15, x = 2 , 2 1 (mod 15) = 2, 2 2 (mod 15) = 4, 2 3 (mod 15) =8, 2 4 (mod 15) = 1 , 2 5 (mod 15) = 2, 2 6 (mod 15) = 4, 2 7 (mod 15) = 8,.. r can be found out using Quantum Phase Estimation algorithm where U is a unitary matrix and is its eigen value and | is its eigen vector In order to measure 𝜃, we need to know about Quantum Fourier Transform (its inverse) and Continued Fraction to extract the period r from 𝜃  

17. 17 Getting period ‘r’ – QPE Quantum phase estimation algorithm  (also referred to as  quantum eigenvalue estimation algorithm ), is a  quantum algorithm  to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. where U is a unitary operator and is its eigen value and | is its eigen vector   Circuit for QPE Phase (counting or t or m ) register needs 2 ⌈log 2 ​N⌉ qubits (determines the accuracy and probability of success) Work register (or m) (holds ∣𝑦⟩) needs log 2 ​N qubits U can be arrived at different ways – permutation matrix, modular multiplication (scalable) Ideally the work register should represent an eigen state of U. The state ∣1⟩ ie . ∣…0001⟩ is used because it is an equal superposition of all the ψ s ​ eigenstates The normalization factors of 1/√2 and QFT inverse are not shown in the figure Quantum Computation and Quantum Information by Michael A Nielsen and Isaax L. Chuang

18. 18 Arrive at U – permutation matrix Build a permutation matrix y x y’. It is also a unitary matrix Label the 2 𝑛 computational basis states by integers 𝑦 ∈ {0,1,…,2 n −1 }, y’ N – the number to be prime factored, a guess integer For N = 3, a = 2, compute f(y) = (2⋅y) mod 3 for y < 3 else leave y unchanged y 2⋅y (mod3) y′ Row y’, column y y′ = 0 → U 0,0 = 1 1 2 2 y′ = 2 → U 2,1 = 1 2 4 mod  3 = 1 1 y′ = 1 → U 1,2 = 1 3 — 3 y′ = 3 → U 3,3 = 1 Even though the values in the matrix are just 0 or 1, the pattern is unique for each pair (𝑎,𝑁) since y ′ =( a⋅y ) mod N For power = 2

19. 19 Arrive at U – modular multiplication Modular addition Controlled modular addition Modular multiplication (with control) Modular exponentiation Quantum Phase Estimation (QPE) Inverse QFT (with bit reversal if needed)

20. 20 Getting period ‘r’ – continued fraction We get s/r from the measurement (and dividing by 2 m ) from QFT. Even though 𝑠 is random, its denominator is always the true period 𝑟. In the rare cases where gcd ⁡( s,r ) > 1, you might get a reduced fraction s′/r​ with r′< r, then you discard and repeat. But the success probability per run is high enough that a constant (on average) number of repetitions suffices A continued fraction turns a real number 𝑥 into a sequence of integer “partial quotients” [𝑎0;𝑎1,𝑎2,…  The Fraction class in Python, found within the fractions module, provides the denominator Check that 𝑟 is even and 𝑎 𝑟/2 ≠ −1(mod 𝑁), Compute gcd (𝑎 𝑟/2 ±1, 𝑁) → nontrivial factors of 𝑁. If any check fails, pick a new 𝑎 and repeat

21. 21 Shor’s quantum factoring algorithm Classical Preprocessing Get the number N to be factored Pick a random integer 𝑎, 1<𝑎<𝑁-1, Compute 𝑔 = gcd⁡(𝑎,𝑁) & If 𝑔>1, you’ve already found a nontrivial factor Quantum Period‐Finding Find out the period r such that a r = 1(mod N) using QPE Arrive at the Unitary matrix U ( U:∣y⟩↦∣ay mod N⟩ ) Generate QPE circuit using counting registers, work registers, apply controlled modular exponentiation Add inverse QFT module Measure the counting register ( m bit outcome k & k/2 m ≈ s/r) Classical Postprocessing Use the continued‐fraction algorithm on 𝑘/2 𝑚 to recover the denominator 𝑟 Check that 𝑟 is even and 𝑎 𝑟/2 ≠ −1(mod 𝑁) Compute gcd (𝑎 𝑟/2 ±1, 𝑁) → nontrivial factors of 𝑁 If any check fails, pick a new 𝑎 or repeat Probability of guessing Probability of guessing the right a is where k is the number of distinct odd prime factors of N  

22. 22 Shor’s algorithm - Hands-on

23. 23 Grover’s algorithm What is it? An algorithm proposed by Lov Grover solves the problem of an unstructured search It is a quantum algorithm for finding the input value  x *  of a function f ( x ) with  f(x*) = 1 and  f(x) = 0 for all other values of  x An example for a problem to use this algorithm is finding a phone number in an unsorted telephone directory. You need N (number of entries) steps to get the right answer (on average it may be N/2). With Grover’s algorithm, we can get the answer with a maximum of steps (quadratic speedup) It can also be used in cryptanalysis, optimization, drug discovery, etc.,  

24. 24 Algorithm Steps Represent all the N input states with uniform superposition of all states (with n number of qubits and applying Hadamard gates) by 2 n (N = 2 n ) qubits where n is an integer Define a black-box unitary U that “flips the sign” of the target state(s) Create a diffusion operator D (also called inversion about the mean), it reflects amplitudes through the uniform state ∣𝑠⟩ Repeat the Grover iteration G = D U (do U then do D), k times After k iterations, measure all the qubits, we will get x* or w We must re-apply U every time, because each diffusion step redistributes amplitudes, and you need a fresh phase flip on x∗ before the next inversion-about-mean

25. 25 Building the Oracle U U ∣x⟩ = (−1) f(x) ∣x⟩ With ancilla qubit We flip q₂ so that 011→111. The first 3-controlled X writes a 1 into the ancilla precisely when the data is 111 (i.e. originally 011). A Z on the ancilla kicks back a −1 only onto that branch. Uncomputing and flipping q₂ back leaves the data state 011 marked. Without ancilla qubit We flip q₂ so 011→111. A single CCZ on ( q₂,q₁,q ₀) multiplies |111⟩ by −1. Flipping q₂ back restores all labels but leaves 011 with the −1. When to use which approach? Qubit-scarce device + simple pattern → use direct CCZ. Complex oracle logic or modular functions → use ancilla-based. Hardware with native multi-controls → direct version is very efficient. Hardware with limited multi-controls but many qubits → ancilla version lets you decompose logic into smaller Toffolis Oracle with ancilla qubit Oracle without ancilla qubit

26. 26 Building the Diffusion Operator D Diffusion Operator does “inversion about average” Taking outer product Multiplying by 2 and Subtracting from I, we get D Let us take a sample vector   Average = 0.5

27. 27 Building the Diffusion Operator D Diffusion Operator = H-X-CZ-X-H Applying Hadamard gates Applying X gates, states are swapped Applying CZ gate, phase of all 1 one state will be flipped Applying X gates again, states are swapped Applying H gates, the amplitude of marked state increases State Initial After Oracle After H After X After (CZ) After X Final (After H) ∣00⟩ 0.5 0.5 0.5 0.5 0.5 -0.5 ∣01⟩ 0.5 -0.5 0.5 -0.5 -0.5 0.5 -1 ∣10⟩ 0.5 0.5 -0.5 0.5 0.5 -0.5 ∣11⟩ 0.5 0.5 0.5 0.5 -0.5 0.5 Qubit States at each DO stage

28. 28 Algorithm Steps Grover has given ways to improve (amplify) this amplitude       Amplitude Data   N               Amplitude Data <   N Rotating with respect to      

29. 29 Algorithm Steps Amplitude Data <   N Rotating U with respect to                      

30. 30 Grover’s algorithm - Hands-on

31. 31 References Text book Quantum Computation and Quantum Information by Michael A Nielsen and Isaax L. Chuang IBM online documents https://quantum.cloud.ibm.com/learning/en/courses/basics-of-quantum-information/single-systems/introduction https://quantum.cloud.ibm.com/docs/en/guides YouTube videos https://www.youtube.com/playlist?list=PL49CF3715CB9EF31D https://www.youtube.com/@SKathiresan https://www.youtube.com/watch?v=3-c4xJa7Flk&t=111s

32. THANK YOU

33. Q & A