Simon's Algorithm: Solving the Mystery of f(x+s)

Click For Summary
SUMMARY

Simon's Algorithm is a quantum algorithm designed to determine a secret string s when provided with a black box function f that computes f(x+s) using bit-wise modulo 2 addition. The algorithm requires n-1 equations to effectively identify the secret string, which may seem excessive given that a single input can reveal s. However, the necessity of multiple equations arises from the algorithm's ability to handle more complex functions beyond simple bitwise addition, allowing it to explore all n! permutations of potential outputs. This complexity is crucial for leveraging the full power of quantum computing in solving problems that classical algorithms cannot efficiently address.

PREREQUISITES
  • Understanding of quantum computing principles
  • Familiarity with qubits and their representation
  • Knowledge of black box functions in computational theory
  • Basic grasp of modulo operations and bitwise arithmetic
NEXT STEPS
  • Study the implementation of Simon's Algorithm in quantum programming languages like Qiskit
  • Explore the concept of quantum superposition and entanglement
  • Learn about the implications of Simon's Algorithm in cryptography
  • Investigate other quantum algorithms, such as Grover's Algorithm, for comparative analysis
USEFUL FOR

Quantum computing enthusiasts, researchers in computational theory, cryptographers, and anyone interested in advanced algorithms that exploit quantum mechanics for problem-solving.

Aakash Lakshmanan
Messages
9
Reaction score
0
Hi all, I am sure some of you have heard of Simon's algorithm that calculates a secret string s when given a black box. Basically, let's say we have a qubit x that is n digits long. Now the black box contains a function f that outputs f(x+s) where s is the mystery string and + is bit-wise modulo 2 addition. For Simon's algorithm, you apparently need like n-1 equations and stuff but I don't understand why this is necessary. For example, let's say the secret string s=101.

Then if input was 000, we have 101

From here, we already know the secret string. What is the purpose of going any further, is it not trivial what this secret string is? Can someone please explain this to me?
 
Physics news on Phys.org
At least according to the wikipedia description, the function can be much more general than just bitwise addition. As a subset (!), all n! permutations are possible.
 

Similar threads

Undergrad Arithmetic Block in Shor Algorithm
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Shor's algorithm - need to uncompute auxiliary qubits?
  • · Replies 2 ·
Replies
2
Views
3K
Graduate Shor's algorithm and similar exploitation of QM?
  • · Replies 11 ·
Replies
11
Views
3K
Undergrad Measurement of a qubit in the computational basis - Phase estimation
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad HHL Algorithm for Solving Linear Equations
  • · Replies 1 ·
Replies
1
Views
2K
High School Quantum computer vs supercomputer performance
  • · Replies 8 ·
Replies
8
Views
3K
MHB Can Turing Machine Decidability Extend to Complex Algorithm Outputs?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Trouble with a passage in Zariski & Samuel's Commutative algebra text
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Can anyone give me the details of creating a cat state in Circuit QED?
  • · Replies 16 ·
Replies
16
Views
4K
Undergrad Quantum Computing and Superposition of states
  • · Replies 5 ·
Replies
5
Views
2K