Most developers on Amazon Braket interested in quantum computing often depend on current algorithms to study the fundamentals. Like Simon’s algorithm, these algorithms are included in Amazon Braket’s SDK and managed notebooks.
Designed by Daniel Simon, a Principal Security Engineer in the AWS Cryptography group, Simon’s algorithm solves the Simon problem. This computational problem can be solved exponentially quicker on a quantum computer than on a classical computer. It employs a linear number of questions other than an exponential number of queries like classical methods.
This article will look at Simon’s algorithm, one of the earliest quantum algorithms developed and a new addition to Amazon Braket.
Simon’s Problem
Simon’s algorithm was designed to solve a specific mathematical problem in which there is a function “f”:{0,1}n→{0,1}n that maps bit strings to bit strings with the promise that the function “f” either maps each unique input to a unique output or maps two distinct inputs to a single unique output.
This suggests that “f” is either one-to-one or two-to-one and that the promise has been granted. Simon’s algorithm discovers if “f” is one-to-one or two-to-one by finding the secret string “s”. To solve Simon’s problem classically, one has to identify two separate inputs or demonstrate that no two inputs generate the same result.
But Simon, the creator, says this may not always be true. According to him, some magical algorithm may always locate the string “s” efficiently by digging about in the details of the calculation of “f”.
Simon’s Algorithm
Simon’s algorithm, which combines quantum and classical elements, was the first quantum algorithm to solve Simon’s problem with exponentially fewer queries to the function “f” compared to the best conventional approach.
First published in 1994, it inspired quantum algorithms based on the quantum Fourier transform, such as Shor’s factoring algorithm, employed in the most renowned quantum algorithm. The quantum component of Simon’s algorithm is used to effectively query the oracle, while the classical component is used to analyze measurement data and find the hidden string “s”.
The unknown function “f” must be implemented using quantum logic to make the algorithm work. In simple terms, you want a unitary operator Uf that represents the operation of the function f on quantum states. In some applications, it is assumed that the unitary Uf is provided as a black box, about which nothing is known except that it executes the preceding transformation.
Implementing Simon’s Algorithm On The Amazon Braket
First, the developer imports a method called simons oracle implemented in the amazon-braket-examples repository. This technique implements a specific quantum oracle for a secret function f. The simons oracle function takes a secret string s that is selected at the beginning.
The python code snippet generates a circuit run using the Amazon Braket local simulator 4n times. The developer then selects the number of shots to be 4n so that, with high probability, at least n linearly independent samples that may be utilized to solve for s are acquired with a high probability.
The remainder of the method results from a set of linear equations that can be solved to obtain the classical string “s”.
Simon’s algorithm has applications in various fields, including cryptography (where it can be used to factorize large numbers), and machine learning, where it can be used to detect patterns in data.
Conclusion
Simon’s algorithm is an important foundational concept in quantum information theory and quantum computation. It is often taught to students as part of the core curriculum because it can be easily understood quickly. Despite its simplicity, the ideas behind Simon’s algorithm have had a lasting impact and can be found in many modern quantum algorithms.
