Quantum Query Algorithms

Quantum Query Algorithms Walid Gomaa Department of Computer Science and Engineering, Egypt Japan University of Science and Technology Walid Gomaa Quantum Computing November 7, 2025 Overview 1Introduction 2Deutsch’s Problem 3Phase Kickback 4The Deutsch-Jozsa Problem 5The Bernstein-Vazirani Problem 6Simon’s Problem Walid Gomaa Quantum Computing November 7, 2025 Introduction Introduction Introduction Walid Gomaa Quantum Computing November 7, 2025 Introduction Standard Model of Computation Standard abstraction of computation looks like this: Different specific models of computation are studied, including Turing machines and Boolean circuits . Observation The entire input is provided to the computation — most typically as a string of bits — with nothing being hidden from the computation. Walid Gomaa Quantum Computing November 7, 2025 Introduction Query Model of Computation Query model of computation: input is made available in the form of a function , which the computation accesses by making queries . Walid Gomaa Quantum Computing November 7, 2025 Introduction Query Model of Computation The input to query problems is represented by a function: f: Σn→Σm where m,n∈N>0and Σ = {0,1}. Queries A computation makes a query: submitting a query to the function oracle f: x∈ {0,1}nis selected, and the string f(x)∈ {0,1}mis made available to the computation. Measure the efficiency of query algorithms by counting the number of queries submitted to the oracle f. Walid Gomaa Quantum Computing November 7, 2025 Introduction Examples Logical OR Input oracle: f:{0,1}n→ {0,1} Output: (1 if ∃x∈ {0,1}nsuch that f(x)=1 0 otherwise Parity (XOR) Input: f:{0,1}n→ {0,1} Output: (0|{x:f(x)=1}| ≡ 0 (mod 2) 1|{x:f(x)=1}| ≡ 1 (mod 2) Walid Gomaa Quantum Computing November 7, 2025 Introduction Examples Minimum Input: f:{0,1}n→ {0,1}m Output: The string y∈ {f(x) : x∈ {0,1n}that comes first in the lexicographic ordering of {0,1}m(viewing bit strings as integers, find min{y:y∈range(f)}) Unique search ( promise problem ) Input: f:{0,1}n→ {0,1} Promise: |{x:f(x) = 1}}| = 1 Output: z:f(z) = 1 Walid Gomaa Quantum Computing November 7, 2025 Introduction Query Gates For circuit models of computation, queries are made by query gates . For Boolean circuits, query gates generally compute the input function fdirectly: For example, the following circuit computes Parity for every f:{0,1}→{0,1}: Walid Gomaa Quantum Computing November 7, 2025 Deutsch’s Problem Deutsch’s Algorithm Deutsch’s algorithm solves Deutsch’s problem using a single query: |π1⟩=1 2(|0⟩−|1⟩)|0⟩+1 2(|0⟩−|1⟩)|1⟩Uf(|y⟩|x⟩) = |y⊕f(x)⟩|x⟩ |π2⟩=1 2(|0⊕f(0)⟩−|1⊕f(0)⟩)|0⟩+1 2(|0⊕f(1)⟩−|1⊕f(1)⟩)|1⟩ Walid Gomaa Quantum Computing November 7, 2025 Deutsch’s Problem Deutsch’s Algorithm Deutsch’s algorithm solves Deutsch’s problem using a single query: |π2⟩=1 2(|0⊕f(0)⟩−|1⊕f(0)⟩)|0⟩+1 2(|0⊕f(1)⟩−|1⊕f(1)⟩)|1⟩ =1 2(−1)f(0)(|0⟩−|1⟩)|0⟩+1 2(−1)f(1)(|0⟩−|1⟩)|1⟩ =|−⟩(−1)f(0)|0⟩+ (−1)f(1)|1⟩ √2 Walid Gomaa Quantum Computing November 7, 2025 Deutsch’s Problem Deutsch’s Algorithm Deutsch’s algorithm solves Deutsch’s problem using a single query: |π2⟩=|−⟩(−1)f(0)|0⟩+ (−1)f(1)|1⟩ √2= (−1)f(0)|−⟩|0⟩+ (−1)f(0)⊕f(1)|1⟩ √2 =((−1)f(0)|−⟩|+⟩f(0) ⊕f(1) = 0 (fis constant) (−1)f(0)|−⟩|−⟩ f(0) ⊕f(1) = 1 (fis balanced) Walid Gomaa Quantum Computing November 7, 2025 Deutsch’s Problem Deutsch’s Algorithm Deutsch’s algorithm solves Deutsch’s problem using a single query: |π2⟩=((−1)f(0)|−⟩|+⟩f(0) ⊕f(1) = 0 (fis constant) (−1)f(0)|−⟩|−⟩ f(0) ⊕f(1) = 1 (fis balanced) |π3⟩=((−1)f(0) |−⟩|0⟩f(0) ⊕f(1) = 0 (fis constant) (−1)f(0) |−⟩|1⟩f(0) ⊕f(1) = 1 (fis balanced) Walid Gomaa Quantum Computing November 7, 2025 Deutsch’s Problem Deutsch’s Algorithm Deutsch’s algorithm solves Deutsch’s problem using a single query: |π3⟩=((−1)f(0) |−⟩|0⟩f(0) ⊕f(1) = 0 (fis constant) (−1)f(0) |−⟩|1⟩f(0) ⊕f(1) = 1 (fis balanced) = (−1)f(0) |−⟩|f(0) ⊕f(1)⟩ Walid Gomaa Quantum Computing November 7, 2025 Phase Kickback Phase Kickback Phase Kickback Walid Gomaa Quantum Computing November 7, 2025 Phase Kickback Phase Kickback in Quantum Computing I A fundamental concept in quantum computing, particularly in quantum algorithms that involve quantum phase estimation. The quantum phase kickback effect occurs when a controlled-unitary operation imparts a phase shift on the control qubit rather than altering the target qubit. Phase information is said to “kick back” from the target register to the control register. Walid Gomaa Quantum Computing November 7, 2025 Phase Kickback Phase Kickback Mathematical Derivation CU(|x⟩|y⟩) = |x⟩Ux|y⟩ If |y⟩is an eigenstate of Uwith eigenvalue e2πiϕ, then: CU(|x⟩|y⟩) = e2πixϕ|x⟩|y⟩ ⇒The phase e2πiϕis transferred to the control qubit. Walid Gomaa Quantum Computing November 7, 2025 Phase Kickback Phase Kickback Example: Controlled-Phase Gate Pθ=1 0 0eiθ CPθ(|+⟩|1⟩) = 1 √2|0⟩|1⟩+eiθ|1⟩|1⟩ ⇒Target remains |1⟩,control acquires the phase eiθ. Walid Gomaa Quantum Computing November 7, 2025 Phase Kickback Phase Kickback |b⊕c⟩=Xc|b⟩Xis the Pauli NOT operator; X1means the operator is applied Uf(|b⟩|a⟩) = |b⊕f(a)⟩|a⟩= (Xf(a)|b⟩)|a⟩ Uf(|ψ⟩|a⟩)=(Xf(a)|ψ⟩)|a⟩by linearity Uf(|−⟩|a⟩)=(Xf(a)|−⟩)|a⟩= (−1)f(a)|−⟩|a⟩choose |ψ⟩=|−⟩,X|−⟩ =− |−⟩ (|−⟩ eigenvector of Xwith eigenvalue −1) Uf(|−⟩|a⟩)=(−1)f(a)|−⟩|a⟩phase kickback Walid Gomaa Quantum Computing November 7, 2025 The Deutsch-Jozsa Problem Deutsch-Jozsa Analysis Some tricks Hadamard transofmr on nqubit (superposition of all 2nstates with equal proportions, and different relative phases): H⊗n|xn−1···x1x0⟩= (H|xn−1⟩)⊗···⊗(H|x0⟩) =  1 √2X yn−1∈{0,1} (−1)xn−1yn−1|yn−1⟩ ⊗···⊗  1 √2X y0∈{0,1} (−1)x0y0|y0⟩  =1 √2nX yn−1···y0∈{0,1}n (−1)xn−1yn−1+···+x0y0|yn−1···y0⟩=1 √2nX y∈{0,1}n (−1)x·y|y⟩ Walid Gomaa Quantum Computing November 7, 2025 The Deutsch-Jozsa Problem Deutsch-Jozsa Analysis Some tricks H|a⟩=1 √2X b∈{0,1} (−1)ab |b⟩ H⊗n|xn−1···x1x0⟩=1 √2nX y∈{0,1}n (−1)x·y|y⟩ H⊗n|0···0···0⟩=1 √2nX y∈{0,1}n|y⟩(uniform superposition over all states) Walid Gomaa Quantum Computing November 7, 2025 The Deutsch-Jozsa Problem Deutsch-Jozsa Analysis Debugging |π1⟩=|−⟩⊗ 1 √2nX x∈{0,1}n|x⟩ |π2⟩=|−⟩⊗ 1 √2nX x∈{0,1}}n (−1)f(x)|x⟩(using phase oracle) Walid Gomaa Quantum Computing November 7, 2025 The Deutsch-Jozsa Problem Deutsch-Jozsa Analysis Debugging |π2⟩=|−⟩⊗ 1 √2nX x∈{0,1}n (−1)f(x)|x⟩(using phase oracle) |π3⟩=|−⟩⊗ 1 2nX y∈{0,1}nX x∈{0,1}n (−1)f(x)+x·y|y⟩ Walid Gomaa Quantum Computing November 7, 2025 The Deutsch-Jozsa Problem Deutsch-Jozsa Analysis I The probability for the measurements to give y= 0nis p(0n) =  1 2nX x∈{0,1}n (−1)f(x) 2 =(1 if f is constant 0 if f is balanced Algorithm solves the Deutsch-Jozsa problem without error with a single query. Any deterministic algorithm must at least make 2n−1+ 1 queries. Walid Gomaa Quantum Computing November 7, 2025 The Deutsch-Jozsa Problem Deutsch-Jozsa Analysis II Aprobabilistic algorithm can, however, solve the Deutsch-Jozsa problem using just a few queries: 1Choose kinput strings x(1),...,x(k)∈ {0,1}nuniformly at random. 2If f(x(1)) = ··· =f(x(k)), then answer 0 (constant), else answer 1 (balanced). If f is constant, this algorithm is correct with probability 1. If f is balanced, this algorithm is correct with probability 1 −2−k+1. Walid Gomaa Quantum Computing November 7, 2025 The Bernstein-Vazirani Problem The Bernstein-Vazirani Problem Walid Gomaa Quantum Computing November 7, 2025 The Bernstein-Vazirani Problem The Bernstein–Vazirani Problem Bernstein–Vazirani problem Input: f:{0,1}n→ {0,1} Promise: There exists a binary string s=sn−1···s0for which f(x) = s·xfor all x∈ {0,1}n Output: The string s Walid Gomaa Quantum Computing November 7, 2025 The Bernstein-Vazirani Problem The Bernstein–Vazirani Problem |π1⟩=|−⟩⊗ 1 √2nX x∈{0,1}n|x⟩ |π2⟩=|−⟩⊗ 1 √2nX x∈{0,1}n (−1)f(x)|x⟩(using phase oracle - phase quickback) Walid Gomaa Quantum Computing November 7, 2025 The Bernstein-Vazirani Problem The Bernstein–Vazirani Problem |π3⟩=|−⟩⊗ 1 2nX y∈ΣnX x∈Σn (−1)f(x)+x·y|y⟩ =|−⟩⊗ 1 2nX y∈ΣnX x∈Σn (−1)s·x+y·x|y⟩ =|−⟩⊗ 1 2nX y∈ΣnX x∈Σn (−1)(s⊕y)·x|y⟩ =|−⟩⊗|s⟩(s⊕y=0n⇐⇒ s=y) (s·x)⊕(y·x)=(s⊕y)·x (ac)⊕(bc)=(a⊕b)cformula for single bits (s·x)⊕(y·x)=(sn−1xn−1)⊕···⊕(s0x0) ⊕(yn−1xn−1)⊕···⊕(y0x0) = (sn−1⊕yn−1)xn−1⊕···⊕(s0⊕y0)x0 = (s⊕y)·x 1 2nX x∈{0,1}n (−1)z·x=(1 if z= 0n 0 if z= 0n The Deutsch-Jozsa circuit problem with a single query. Any probabilistic algorithm must make at least n queries to find s. Walid Gomaa Quantum Computing November 7, 2025 Simon’s Problem Simon’s problem =1 22nX z∈range(f)X x∈f−1({z}) (−1)x·y 2 range(f) = {f(x) : x∈ {0,1}n} f−1({z}) = {x∈ {0,1}n:f(x) = z} Walid Gomaa Quantum Computing November 7, 2025 Simon’s Problem Case 1: s= 0n p(y) = 1 22nX z∈range(f)X x∈f−1({z}) (−1)x·y 2 fis a one-to-one =⇒there is a single element x∈f−1({z}) for every z∈range(f): X x∈f−1({z}) (−1)x·y 2 = 1 There are 2nelements in range(f), so p(y) = 1 22n·2n=1 2n,∀y∈ {0,1}n Walid Gomaa Quantum Computing November 7, 2025 Simon’s Problem Case 1: s= 0n p(y) = 1 22nX z∈range(f)X x∈f−1({z}) (−1)x·y 2 There are two strings in the set f−1({z}) for each z∈range(f); if w∈f−1({z}), either one of them, then w⊕s is the other. X x∈f−1({z}) (−1)x·y 2 =(−1)w·y+ (−1)(w⊕s)·y 2=|1+(−1)s·y|2 =(4s·y= 0, 0s·y= 1 . Walid Gomaa Quantum Computing November 7, 2025 Simon’s Problem Case 1: s= 0n There are 2n−1elements in range(f), so: p(y) = 1 22nX z∈range(f)X x∈f−1({z}) (−1)x·y 2 =(1 2n−1s·y= 0, 0s·y= 1 . Walid Gomaa Quantum Computing November 7, 2025 Simon’s Problem Classical Post-Processing Running the circuit from Simon’s algorithm one time gives us a random string y∈ {0,1}n. Case 1: s= 0n p(y) = 1 2n Case 1: s= 0n p(y) = (1 2n−1s·y= 0 0s·y= 1 Suppose we run the circuit independently k=n+rtimes, obtaining strings y(1),...,y(k). y(1) =y(1) n−1···y(1) 0 y(2) =y(2) n−1···y(2) 0 . . . y(k)=y(k) n−1···y(k) 0 M=      y1 n−1··· y1 0 y2 n−1··· y2 0 . . ..... . . yk n−1··· yk 0       ,M   sn−1 . . . s0   =   0 . . . 0    Using Gaussian elimination we can efficiently compute the null space (modulo 2) of M. With probability greater than 1 −2−rit will be {0n,s}. Walid Gomaa Quantum Computing November 7, 2025 Simon’s Problem Classical Difficulty Classical Lower Bound Any probabilistic algorithm making fewer than 2n 2−1−1 queries will fail to solve Simon’s problem with probability at least 1/2. Quantum Advantage Simon’s algorithm solves Simon’s problem with a linear number of queries. Classical Limitation Every classical algorithm requires an exponential number of queries. Walid Gomaa Quantum Computing November 7, 2025 Thank You! Questions or comments are welcome. Presented by Walid Gomaa Email: [email protected]