Simon's algorithm efficiently determines a hidden bit string that defines the periodicity of a function, providing an exponential quantum speedup.
Algorithm Details
Simon's algorithm, developed by Daniel Simon in 1994, is a quantum algorithm that solves a specific problem exponentially faster than the best-known classical algorithm1. The problem, known as Simon's problem, is a special case of the more general hidden subgroup problem, which has important applications in cryptography and other areas of computer science.
Problem Target
Simon's problem can be formulated as follows: given a black-box function f(x) that maps an n-bit binary string x to an n-bit binary string y, find a non-zero n-bit string s such that f(x) = f(y) if and only if x ⊕ y = s or x = y, where ⊕ denotes the bitwise XOR operation. In other words, the function f(x) is promised to be either one-to-one or two-to-one, with the latter case having a specific structure determined by the string s.
Quantum ApproachClassically, solving Simon's problem requires Ω(2^(n/2)) queries to the black-box function, as the algorithm needs to find a collision (i.e., two distinct inputs that map to the same output) to determine the string s. However, Simon's algorithm can solve the problem using only O(n) queries to a quantum oracle that implements the function f(x)2.
Implementation Steps
State preparation
Initialise an n-qubit quantum state |ψ⟩ in the |0⟩ state and an n-qubit ancilla register in the |0⟩ state.
Apply Hadamard gates
Apply a Hadamard gate to each of the n qubits in the |ψ⟩ state. This creates a superposition of all possible n-bit strings.
Oracle query
Apply the quantum oracle that implements the function f(x) to the |ψ⟩ state and the ancilla register. The oracle performs the following transformation: |x⟩|0⟩ → |x⟩|f(x)⟩ which entangles the |ψ⟩ state with the ancilla register, encoding the structure of the function f(x) into the quantum state.
Measure the ancilla register
Measure the ancilla register in the computational basis and discard the result. This step disentangles the |ψ⟩ state from the ancilla register and collapses the quantum state into a superposition of input strings that map to the same output string.
Apply Hadamard gates
Apply a Hadamard gate to each of the n qubits in the |ψ⟩ state. This step transforms the quantum state into a superposition of states that encode information about the string s.
Measure the state
Measure the |ψ⟩ state in the computational basis, obtaining an n-bit string y.
Classical post-processing
Repeat steps 1-6 O(n) times to obtain a set of n-bit strings {y_i}. Solve the system of linear equations y_i · s = 0 (mod 2) to determine the string s.
Practical Applications
Simon's algorithm achieves an exponential speedup over classical algorithms by exploiting the properties of quantum superposition and entanglement4. The quantum oracle creates a superposition of input-output pairs, which allows the algorithm to probe the structure of the function f(x) in parallel. The final measurement and classical post-processing steps extract the information about the string s from the quantum state.
Simon's algorithm has important implications for cryptography, as it demonstrates the potential of quantum computers to break certain classical cryptographic schemes that rely on the hardness of finding collisions in two-to-one functions. In particular, Simon's algorithm inspired the development of Shor's algorithm for factoring large integers, which poses a threat to the widely-used RSA cryptographic system5.
Simon's algorithm has been experimentally demonstrated on various quantum computing platforms, including nuclear magnetic resonance (NMR), superconducting, and photonic qubits. These experimental realisations have validated the principles of the algorithm and have paved the way for the development of more complex quantum algorithms.
Implementation Challenges
The algorithm's scope is confined to a specific problem domain. It excels at identifying a hidden bit string 's' given a particular type of function with a certain structure. While demonstrating exponential speedup in this scenario, it doesn't directly translate to solving arbitrary computational problems6.
Simon's algorithm, like many quantum algorithms, relies on the existence of a quantum oracle capable of evaluating the function efficiently. While such oracles are theoretically possible, constructing them for real-world scenarios can be a daunting task. Consequently, Simon's algorithm finds limited practical applications beyond showcasing the theoretical potential of quantum computing. Its real-world relevance is currently constrained by its narrow focus and the challenge of constructing suitable oracles. Furthermore, the algorithm is susceptible to errors stemming from noise and decoherence in quantum systems. These errors can accumulate as the problem size grows, affecting the accuracy and reliability of the results7.
Bottom Line
Simon's algorithm is a quantum algorithm that solves a specific problem exponentially faster than the best-known classical algorithm. It demonstrates the power of quantum computing in tackling certain problems with a clear quantum advantage and has important implications for cryptography and other areas of computer science. Simon's algorithm has also inspired further research in quantum algorithms and has contributed to the development of more advanced quantum algorithms, such as Shor's algorithm.
References
-
Simon, D. R. (1997). On the power of quantum computation. SIAM Journal on Computing, 26(5), 1474-1483.
-
Jozsa, R. (2001). Quantum factoring, discrete logarithms, and the hidden subgroup problem. Computing in Science & Engineering, 3(2), 34-43.
-
Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press.
-
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5), 1510-1523.
-
Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science, 124-134.
-
Aaronson, S., & Ambainis, A. (2009). The need for structure in quantum speedups. Theory of Computing, 10(6), 133-166.
-
Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. Quantum, 2, 79.