Academy K

Simon's Algorithm Implementation

InterviewCodingSimon's algorithmhidden subgrouplinear algebra

Related module: Early algorithms

Problem statement

Simon's algorithm finds a hidden string ss such that f(x)=f(y)f(x) = f(y) iff x⊕y∈{0,s}x \oplus y \in \{0, s\} for a function f:{0,1}n→{0,1}nf:\{0,1\}^n \to \{0,1\}^n.

  1. Describe the quantum circuit.
  2. What classical post-processing is needed?
  3. Write pseudocode for the full algorithm.

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.