Hidden Shift Algorithm

Hidden Shift Algorithm

The Hidden Shift Problem is one of the known problems for which a quantum algorithm achieves an exponential speedup over the best classical approach, and this Cirq example demonstrates a circuit that solves it. The setup involves two Boolean functions f and g that are identical up to an unknown shift by a hidden bit string s, so that g(x) = f(x XOR s) for every input x; the goal is to recover s. Much of the quantum advantage comes from the ability to perform Fourier transforms over the Boolean cube efficiently, which lets the algorithm extract correlations between the two functions that are inaccessible to classical querying. The example implements the algorithm for bent functions, a special class with flat Fourier spectra that makes the shift cleanly recoverable: it prepares a superposition, queries the two functions, applies Hadamard (Fourier) transforms to interfere the amplitudes, and measures to read out the hidden shift in a single shot. The script constructs the functions and the planted shift, builds and simulates the circuit, and verifies that the recovered string matches. It is an instructive example of how efficient quantum Fourier sampling turns a hidden-structure problem into a fast measurement.

Run it

pip install -r requirements.txt
python hidden_shift_algorithm.py

Source and license

Imported from examples/hidden_shift_algorithm.py in quantumlib/Cirq at v1.6.1, under the Apache License 2.0. Original authors: The Cirq Developers. The upstream LICENSE is included alongside this example.