This note is part of [[quantum/Practical Quantum Information System]]. > [!info] Course code > Use the companion repository for this lecture's runnable lab, helper functions, and regression checks: > - [notebooks/by_concept/bernstein_vazirani_and_simons_algorithm.ipynb](https://github.com/montekkundan/quantum-code/blob/main/notebooks/by_concept/bernstein_vazirani_and_simons_algorithm.ipynb) > - [qcourse/oracles.py](https://github.com/montekkundan/quantum-code/blob/main/qcourse/oracles.py) > - [tests/test_expanded_course_primitives.py](https://github.com/montekkundan/quantum-code/blob/main/tests/test_expanded_course_primitives.py) [TODO: add video - Bernstein-Vazirani and Simon's Algorithm] ## What This Concept Is Bernstein-Vazirani and Simon's algorithm are the next step after Deutsch-Jozsa in the oracle story. They show that once you understand how to encode global structure into phase and then read it out through interference, you can solve problems that look much less trivial than constant-versus-balanced testing. Bernstein-Vazirani is the clean algebraic version: recover a hidden bit string in one quantum query. Simon's algorithm is the more historically important version: discover a hidden XOR period. Simon's problem is especially valuable because it points directly toward the period-finding structure that later culminates in Shor's algorithm. ## Foundation Terms You Need First An [[quantum/Glossary#Oracle|oracle]] hides the structure you want to recover. [[quantum/Glossary#Query complexity|Query complexity]] counts oracle access. The hidden string in Bernstein-Vazirani and the hidden XOR relation in Simon's problem are both examples of global structure that can be exposed by interference instead of brute-force case inspection. The critical habit is to separate "what the oracle is hiding" from "how the quantum circuit makes that hidden structure observable." ## How The Idea Actually Works In Bernstein-Vazirani, the oracle encodes a secret string $s$. The circuit is built so that one query imprints the relevant parity information into phase, and a final layer of Hadamards converts that phase information into the computational basis, revealing $s$ directly. Simon's problem is subtler. The oracle hides a secret string $s$ such that the function obeys $f(x)=f(x \oplus s)$. The quantum circuit does not output $s$ directly. Instead, repeated runs produce linear equations satisfied by $s$. A small classical linear-algebra step at the end recovers the hidden string. That hybrid structure is important. Quantum speedups often do not eliminate classical work. They change which part of the problem is hard. In Simon's case, the quantum part creates useful linear constraints efficiently, and the classical part solves the resulting system. Pedagogically, these two algorithms are perfect transition material. They are still oracle algorithms, but they already feel much closer to the structure-extraction logic behind serious quantum algorithms. ## Why It Matters - Bernstein-Vazirani gives a compact and exact query advantage. - Simon's algorithm is one of the clearest stepping stones toward Shor's algorithm. - Both train you to see quantum circuits as structure-recovery tools rather than output generators only. ## Related Questions > [!question] Why is Bernstein-Vazirani a better lesson than its small circuit suggests? >> [!answer] It shows the full oracle-algorithm pattern in miniature: prepare superposition, query coherently, use phase/interference to expose global structure, and measure in a basis where the hidden string appears. > [!question] Why does Simon's algorithm need repeated measurements? >> [!answer] A single run gives one random linear constraint on the hidden string. Repeating the circuit gives enough independent constraints to solve for the hidden XOR period with classical linear algebra. > [!question] How does Simon's algorithm point toward Shor? >> [!answer] Both are hidden-period problems. Simon uses an XOR period over bit strings, while Shor uses periodicity in modular arithmetic. The shared idea is to use quantum interference to sample information about a hidden period, then finish classically. ## Additional Study Notes **Check yourself: one query can expose one global bit** For a Boolean function on one input bit, a one-query quantum algorithm can be arranged to learn $f(0)$, $f(1)$, or the parity $f(0)\oplus f(1)$, but not two of those independent pieces of information at once. **Check yourself: Simon's intermediate superposition is not two outputs** A state like $(|x\rangle+|y\rangle)/\sqrt{2}$ does not let you read both $x$ and $y$ in one shot. Measuring it gives one branch, so Simon's algorithm uses repeated Fourier-style samples instead. **Key fact: hidden-period algorithms are sample generators** Simon's and Shor's algorithms do not simply print the hidden period directly. They generate measurement samples that constrain the hidden period, then classical post-processing extracts it. **Question: Why is the parity bit learnable with one quantum query in the tiny Deutsch setting?** The oracle can be used in phase form so that the relative phase after one query depends on whether $f(0)$ and $f(1)$ agree or differ. A final Hadamard turns that relative phase into a computational-basis outcome. ## Study Checks Use these after the explanation, not before it. ### Quick Checks - MCQ: Bernstein-Vazirani finds what hidden object? A. A hidden period in modular arithmetic B. A hidden string in a linear Boolean function C. A marked item in an unstructured database D. A stabilizer generator **Answer:** B. A hidden string in a linear Boolean function. - What is Simon's algorithm trying to recover? **Answer:** A hidden xor mask s such that f(x)=f(y) exactly when x xor y is either 0 or s. ### Oral Exam Anchors > [!question] Oral exam anchor > Explain Bernstein-Vazirani and why it is cleaner than Deutsch-Jozsa. A good answer should say: Bernstein-Vazirani gives oracle access to a function f_s(x)=s dot x mod 2 for an unknown hidden string s. The quantum algorithm prepares a uniform superposition, uses phase kickback to write (-1)^{s dot x} into the amplitudes, and then applies Hadamards. The final state is |s>, so measuring reveals the entire hidden string in one oracle query. It is cleaner than Deutsch-Jozsa because the output is not only a promised classification. The algorithm recovers a concrete hidden object. It also makes phase kickback very explicit, which is why it is a good bridge from basic interference to more advanced hidden-structure algorithms. **Explain Simon's algorithm and its relationship to Shor's algorithm.** A good answer should say: Simon receives oracle access to a function with the promise that f(x)=f(y) exactly when x xor y is either 0 or a hidden string s. The quantum algorithm samples strings z satisfying z dot s = 0 over GF(2). Repeating the procedure gives linear equations, and classical Gaussian elimination recovers s. The relationship to Shor is conceptual. Simon finds hidden xor-period structure, while Shor finds periodic structure in modular arithmetic. In both cases, the quantum part samples information about a hidden structure, and the classical part performs post-processing to recover the object of interest. ## Practical Lab Use this note to practice the shift from oracle outputs to hidden algebraic structure. - Implement Bernstein-Vazirani and verify hidden-string recovery in one logical query. - Implement a small Simon instance on a simulator. - Solve the post-processing equations from your measurement samples to recover the hidden relation. ## Homework Connect the circuits to the underlying algebra. - Explain why Bernstein-Vazirani succeeds with one oracle query. - Describe the hidden structure Simon's algorithm is trying to recover. - Show how the measurement equations in Simon's algorithm lead to the final answer. ## References - Scott Aaronson, [Introduction to Quantum Information Science](https://www.scottaaronson.com/qclec.pdf), Lecture 18. - Ryan O'Donnell, [15-859BB: Quantum Computation and Information](https://www.cs.cmu.edu/~odonnell/quantum15/). - IBM Quantum Learning, [learning portal](https://quantum.cloud.ibm.com/learning/en). - Qiskit documentation, [main docs](https://qiskit.org/documentation/).