ℏQuantum Algorithms

COMPUTATIONAL COMPLEXITY AND SPEEDUPS QUANTUM ALGORITHMS Harnessing Global Coherence and Interference for Speedups An axiomatic summary mapping the foundational quantum query algorithms and complexity boundaries.

1. CORE MECHANICS OF QUANTUM ACCELERATION Quantum algorithms do not simply try all possible answers in parallel. Instead, they utilize the global quantum coherence of an N-qubit register to construct massive superpositions, applying structured unitary gates to evaluate a mathematical function simultaneously across all inputs. The Phase Kickback Mechanism: Many quantum algorithms encode black-box function properties (f(x)) into quantum phases using a controlled Oracle operator Uf. If an auxiliary target qubit is prepared in the state |−⟩= |0⟩−|1⟩√ , the transformation applies a global sign shift directly to the control state: 2 Uf |x⟩⊗|0⟩−|1⟩√ = (−1)f(x) |x⟩⊗|0⟩−|1⟩√ 2 2 Constructive and destructive interference routines are then deployed to amplify the target answer’s probability amplitude while canceling incorrect states.

2. DETERMINISTIC QUERY SPEEDUPS: DEUTSCH-JOZSA The Deutsch-Jozsa algorithm solves a promise problem regarding a hidden function f : {0, 1}n →{0, 1}. The function is guaranteed to be either constant (same output for all inputs) or balanced (exactly half return 0, half return 1). ✦Classical Boundary: Requires evaluating at least 2n−1 + 1 inputs in the worst-case scenario. ✦Quantum Bound: Solves the problem deterministically using exactly 1 query. After phase kickback, applying a global Hadamard transform H⊗n collapses the register to |0⟩⊗n if f is constant, or a state orthogonal to it if f is balanced.

3. QUADRATIC SUBLINEAR SEARCH: GROVER’S ALGORITHM Grover’s algorithm searches an unstructured database of N = 2n items to locate a unique target entry |ω⟩matching f(ω) = 1. The Grover Iterator: Composed of the Oracle operator Uω = I −2 |ω⟩⟨ω| and the Diffusion operator D = 2 |+⟩⟨+|−I, which executes a geometric reflection about the average amplitude. GEOMETRIC AMPLITUDE AMPLIFICATION √ Each iteration rotates the state vector toward the target item by an angle θ ≈2/ N. The optimal number of oracle queries required to maximize the probability of success is upper-bounded by: R ≈π √ N =⇒ Complexity Shift: O(N) Classical −→O(√ N) Quantum 4

4. EXPONENTIAL SPEEDUPS: SHOR’S FACTORING ALGORITHM Shor’s algorithm factors a composite integer M in polynomial time, placing the security of classical RSA encryption into the BQP computational complexity class. It reduces the factoring challenge to a hidden period-finding problem for the function f(x) = ax (mod M).

1. Quantum Parallelism: Generates a massive state superposition mapping √ 1 Px |x⟩|ax (mod M)⟩. 2m

2. The Quantum Fourier Transform (QFT): Extracts the hidden operational period r by evaluating the expo- nential phase shifts across a cyclic matrix structure: N−1 1 QFT |x⟩= √ X e2πixy/N |y⟩ =⇒ Runtime: O((log M)3) vs. Classical O exp c 3p log M N y=0