Simon algorithm is one of the initial quantum algorithms that establish the advantage of quantum computing over classical computing for specific problems. It was proposed by Daniel Simon in 1994 and set the stage for later breakthroughs such as Shor’s factoring algorithm. Simon’s algorithm solves a specific problem, called Simon’s Problem, exponentially faster than any classical deterministic algorithm.
Simon’s Problem
Simon’s problem is a challenge where we are tasked with determining a hidden string s in the presence of a black-box function f that exhibits specific properties.
- Input: A black-box function f:{0,1}n→{0,1}m where n and m are dimensions of the binary inputs and outputs, respectively.
- Promise: There exists a hidden string s∈{0,1}n, such that: f(x)=f(y) ⟺ x⊕y=s, where ⊕ represents the bitwise XOR operation.
- f is a 2-to-1 function under this promise, meaning that for every output of f, there are exactly two inputs x and y (related by x⊕y=s) that produce the same output.
- Output: Identify the hidden string s.
Simon’s Problem Solving Model
Simon’s issue is resolved with an exponential speedup over conventional methods by use of a quantum algorithm using superposition and interference and quantum Fourier transform. Simon’s method consists on using Hadamard gates, querying a black box function, and doing measurements to extract knowledge about a hidden structure within the function.
step-by-step of Simon’s problem solving model
- Problem Setup:
- A function f is given which maps n-bit strings to n-bit strings, i.e., f: {0, 1}n → {0, 1}n.
- The function f is guaranteed to be 2-to-1, with a hidden n-bit string s such that f(x) = f(y) if and only if x = y or x = y ⊕ s, where ⊕ denotes the bitwise XOR operation. The goal is to find s.
- The problem can be generalized such that f(x) = f(y) if and only if x – y is in a subspace S of {0, 1}n over Z2.
- Quantum Circuit Initialization:
- Two registers of n qubits are initialized. The first register is set to |0⟩⊗n, and the second register to |0⟩⊗n.
- A Hadamard transform is applied to the first register, creating an equal superposition of all possible n-bit strings: (1/√2n)∑x∈{0,1}n|x⟩|0⟩.
- Querying the Function:
- The quantum black box function Uf is applied. This function maps |x⟩|b⟩ to |x⟩|b ⊕ f(x)⟩, effectively computing f(x) and storing it in the second register: ∑x∈{0,1}n|x⟩|f(x)⟩.
- Note: The second register may be measured at this point but it is not necessary for the algorithm.
- Second Hadamard Transform:
- A Hadamard transform is applied to the first register again. This step is crucial for the interference that leads to the solution.
- Measurement:
- The first register is measured, yielding an n-bit string w. This w is guaranteed to be orthogonal to s (i.e., w ⋅ s = 0 mod 2), meaning the bitwise dot product of w and s is equal to zero.
- Finding the Hidden String or Subspace:
- The method is run O(n) times to generate n-1 linearly independent strings, wi.
- We solve a set of linear equations WsT = 0T to identify the concealed string s. The measured strings wi form rows in the matrix W. The subspace orthogonal to the subspace the wi spans is the solution space.
- We search for a basis for the hidden subspace in the generalized form of the issue where the hidden structure is a subspace and may then confirm that we have located it by means of more inquiries to the function.
Classical Solution for Simon’s Algorithm
Simon’s problem may be solved using a randomized algorithm based on the “birthday paradox” in classical method.
- The Birthday Paradox: The “birthday paradox” is the phenomena whereby two persons in a really small group have a shockingly high chance of sharing the same birthday. Simon’s dilemma is approached historically using this idea.
- Random Queries: The traditional method makes arbitrary inquiries of the function f. The function receives an n-bit string as input and generates still another n-bit string as output.
- Finding Collisions: Finding a “collision,” or the result of two distinct input strings, i and j, producing the identical output, f(i) = f(j), is the aim. The issue description suggests that this will happen where s is the secret string and i = j ⊕ s.
- Number of Queries: An average of O(√2n) searches is required of a traditional randomized method to identify such a collision. More exactly, the method expects one collision by means of about √2n+1 searches. This is thus because, assuming uniform random distribution of the outputs, each pair of searches has a chance of 1/2n and the number of pairs of searches is quadratic in the number of inquiries.
- Lower Bound: It is shown that any classical randomized method finding s with good probability must undertake Ω(√2n) searches. The conventional method therefore reaches the ideal query complexity.
Simon’s quantum algorithm solves the issue with an estimated number of O(n) searches, therefore showing an exponential speedup in query complexity compared with the classical method.
Time complexity of Simon’s algorithm
Simon’s algorithm’s time complexity may be examined in terms of query complexity and the total number of elementary operations.
Query Complexity
- Quantum Algorithm: Simon’s quantum method calls for an anticipated number of O(n) searches to the function f, where n is the bits count in the input string. This is a major advance over conventional methods.
- Classical Algorithm: To discover the hidden string s Simon’s issue requires an average of O(√2n) searches. It is shown that to solve the issue with good probability any classical randomized method requires at least Ω(√2n) searches.
Overall Time Complexity
- Quantum Algorithm: Simon’s method has an overall time complexity including the other elementary processes needed even if the query complexity is O(n). The poisson time complexity of these processes is polyn. There should be O(n3) elementary gates employed. Simon’s algorithm’s general time complexity is thus regarded to be polyn.
- Classical Algorithm: Simon’s issue has an exponential query complexity, so the classical methods for it suggest they need exponential time with regard to the quantity of input bits. They are inappropriate for high values of n as this exponential time complexity causes.
Important Points
- Simon’s method exhibits an exponential speedup in query complexity over conventional methods. The quantum algorithm therefore gets exponentially quicker in terms of the number of searches to the function f as the input size (n) rises.
- Whereas conventional algorithms have exponential time complexity, the quantum algorithm’s general time complexity is poisson.
- Many quantum algorithms employ query complexity as a proxy for the total computing time as the intermediary unitary operations are typically less expensive.
- Though there are also zero-error variants with a limited worst case running time, with a little likelihood of failure, the quantum method has an estimated polyn running time.
- Standardized Simon’s problem is smaller than n – m + 1 in the generalised form of the problem, in which the hidden structure is a subspace, m is the dimension of the subspace.
The major causes of this speedup are the less searches required to the function and the general time complexity stays polyn, therefore highlighting the ability of quantum computation for some kinds of tasks.