hidden_subgroup_problem#
Functionality#
This module contains high-level quantum programs implementing quantum algorithms for hidden subgroup–related problems, such as Hidden Shift algorithm and Simon’s algorithm.
hidden_shift.py#
Callee: HiddenShift
We consider the following problem setting. Let \(f : \{0,1\}^n \rightarrow \{0,1\}\) be a known Boolean function. In addition, we are given access to a black-box oracle implementing a second Boolean function \(g(x) = f(x \oplus s)\), where \(s_0, s_1, \dots, s_{n-1} \in \{0,1\}^n\) is an unknown bit string referred to as the hidden shift.
The task is to determine the hidden shift \(s\) given oracle access to both \(f\) and \(g\). Because the function \(f\) is highly non-linear, recovering \(s\) from the relation \(g(x) = f(x \oplus s)\) is a non-trivial problem for classical algorithms.
The steps for the Hidden Shift algorithm are the following:
Initialize all qubits to the computational zero state:
\[ \ket{\psi_0}_n = \ket{0}^{\otimes n} \]Apply the Hadamard gate to all qubits to create a uniform superposition:
\[ \ket{\psi_1}_n = H^{\otimes n}\ket{\psi_0}_n = \frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n} \ket{x}_n \]Apply the phase oracle \(U_f\), which encodes the Boolean function \(f(x)\) into the phase:
\[ U_f \ket{x}_n = (-1)^{f(x)} \ket{x}_n \]Hence, the state becomes:
\[ \ket{\psi_2}_n = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \ket{x}_n \]Apply the Hadamard gate again to all qubits (Walsh–Hadamard transform):
Using
\[ H^{\otimes n}\ket{x}_n = \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y}\ket{y}_n, \]where \(x \cdot y\) is the bitwise inner product modulo 2, i,e., given \(x=(x_{n-1}, \dots, x_0)_b\) and \(y=(y_{n-1}, \dots, y_0)_b\),
\[ x \cdot y = \sum_{j=0}^{n-1} x_j y_j \mod 2. \]Then, we obtain
\[ \ket{\psi_3}_n = \frac{1}{2^n} \sum_{y=0}^{2^n-1} \left( \sum_{x=0}^{2^n-1} (-1)^{f(x)+x\cdot y} \right) \ket{y}_n \]Define the Walsh–Hadamard spectrum of \(f\) as
\[ \hat{f}(y) = \sum_{x=0}^{2^n-1} (-1)^{f(x)+x\cdot y} \]Then
\[ \ket{\psi_3}_n = \frac{1}{2^n} \sum_{y=0}^{2^n-1} \hat{f}(y)\ket{y}_n \]Apply the oracle \(U_g\), where \(g(x)=f(x\oplus s)\) and \(s\) is the hidden shift:
\[ U_g\ket{y}_n = (-1)^{f(y\oplus s)}\ket{y}_n \]This yields
\[ \ket{\psi_4}_n = \frac{1}{2^n} \sum_{y=0}^{2^n-1} \hat{f}(y)\,(-1)^{f(y\oplus s)} \ket{y}_n \]Under the hidden-shift promise, the phase can be written as
\[ (-1)^{f(y\oplus s)} = (-1)^{f(y)}(-1)^{s\cdot y} \]so that
\[ \ket{\psi_4}_n = \frac{1}{2^n} \sum_{y=0}^{2^n-1} \hat{f}(y)\,(-1)^{s\cdot y} \ket{y}_n \]Apply the Hadamard gate to all qubits for the third time:
\[ \ket{\psi_5}_n = H^{\otimes n}\ket{\psi_4}_n = \frac{1}{2^n\sqrt{2^n}} \sum_{z=0}^{2^n-1} \left( \sum_{y=0}^{2^n-1} \hat{f}(y)(-1)^{y\cdot(z\oplus s)} \right) \ket{z}_n \]By the orthogonality of the Walsh–Hadamard basis,
\[\begin{split} \sum_{y} \hat{f}(y)(-1)^{y\cdot t} = \begin{cases} 2^n, & t=0, \\ 0, & t\neq 0 \end{cases} \end{split}\]Therefore, only the term \(z=s\) survives, and the final state is
\[ \ket{\psi_5}_n = \ket{s}_n \]Measurement:
Measuring all qubits in the computational basis yields the bit string \(s\), which is exactly the hidden shift.
Notes:
In our implementation, the Boolean function \(f\) is chosen to be the bent function defined as
\[ f(x) = \sum_{i=0}^{\frac{n}{2}-1} x_{2i} x_{2i+1} \mod 2 \]where \(x=(x_{n-1}, \dots, x_0)_b\) is the binary representation of the integer \(x\). Especially, the term \(\frac{n}{2}\) assumes that \(n\) is even; otherwise, an functional fault will be raised.
The final state \(\ket{s}_n\) is defined as \(\ket{s_{n-1}}_1\otimes \ket{s_{n-2}}_1 \otimes \cdots \otimes \ket{s_{0}}_1\).
Test expectations:
Measuring all the qubits can directly yield the hidden bit string.
Doc references: [21]
simon.py#
Callable: Simon
Simon’s algorithm, first introduced in Reference [1], was the first quantum algorithm to show an exponential speed-up versus the best classical algorithm in solving a specific problem. This inspired the quantum algorithms based on the quantum Fourier transform, which is used in the most famous quantum algorithm: Shor’s factoring algorithm.
We are given an unknown blackbox function \(f\), which is guaranteed to be either one-to-one (1:1) or two-to-one (2:1), where one-to-one and two-to-one functions have the following properties:
one-to-one: maps exactly one unique output for every input. An example with a function that takes 4 inputs is:
\[ f(0) \mapsto 0, \quad f(1) \mapsto 1, \quad f(2) \mapsto 2, \quad f(3) \mapsto 3 \]two-to-one: maps exactly two inputs to every unique output. An example with a function that takes 4 inputs is:
\[ f(0) \mapsto 0, \quad f(1) \mapsto 1, \quad f(2) \mapsto 0, \quad f(3) \mapsto 1 \]This two-to-one mapping is according to a hidden bitstring \(b\), where: given \(x_1\) and \(x_2\), if \(x_1 \oplus x_2 = b\), then \(f(x_1) = f(x_2)\). For example, in the above two-to-one function, the hidden bitstring is \(b = 10\) since \((00)_b \oplus (10)_b = (10)_b\) and \((01)_b \oplus (11)_b = (10)_b\).
Given this blackbox \(f\), how quickly can we determine if \(f\) is one-to-one or two-to-one? Then, if \(f\) turns out to be two-to-one, how quickly can we determine \(b\)? As it turns out, both cases boil down to the same problem of finding \(b\), where a bitstring of \(b=000\cdots\) represents the one-to-one \(f\).
The quantum circuit that implements Simon’s algorithm is shown below.
Simon’s algorithm circuit (Source: qiskit-community/qiskit-textbook)
The algorithm involves the following steps (note that our implementation omits the measurement operations):
Two \(n\)-qubit input registers are initialized to the zero state:
\[ \ket{\psi_0}_{2n} = \ket{0}^{\otimes n} \otimes \ket{0}^{\otimes n}. \]Apply a Hadamard transform to the second register:
\[ \ket{\psi_1}_{2n} = \left(I^{\otimes n} \otimes H^{\otimes n}\right) \ket{\psi_0}_{2n} = \frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n} \ket{0}_n \otimes \ket{x}_n. \]Apply the query function \(Q_f\), where \(Q_f: \ket{a}\ket{x} \mapsto \ket{a \oplus f(x)}\ket{x}\). The joint state becomes:
\[ \ket{\psi_2}_{2n} = Q_f \ket{\psi_1}_{2n} = \frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n} \ket{f(x)}_n \otimes \ket{x}_n. \]Apply Hadamard gates to the first register:
\[ \ket{\psi_3}_{2n} = \left(H^{\otimes n} \otimes I^{\otimes n}\right) \ket{\psi_2}_{2n}. \]Expanding the Hadamard transform on the first register yields:
\[ \ket{\psi_3}_{2n} = \frac{1}{2^n} \sum_{y\in\{0,1\}^n} \sum_{x\in\{0,1\}^n} (-1)^{y \cdot f(x)} \ket{y}_n \otimes \ket{x}_n, \]where \(y \cdot f(x)\) denotes the bitwise inner product modulo 2.
Using the promise of Simon’s problem, namely that \(f(x) = f(x \oplus b)\) for a hidden string \(b \in \{0,1\}^n\), the amplitudes interfere constructively only for those \(y\) satisfying
\[ y \cdot b = 0 \pmod{2}. \]As a result, the final state is a superposition over basis states \(\ket{y}\) orthogonal to the hidden string \(b\):
\[\begin{split} \ket{\psi_3}_{2n} = \frac{1}{\sqrt{2^{n-1}}} \sum_{\substack{y\in\{0,1\}^n \\ y\cdot b = 0}} \ket{y}_n \otimes \ket{\phi_y}_n, \end{split}\]where \(\ket{\phi_y}_n\) denotes a (generally unobserved) state of the second register.
Repeated executions (\(\approx n\)) of the circuit yield linearly independent vectors \(y\) satisfying \(y \cdot b = 0\), from which the hidden string \(b\) can be reconstructed by solving a system of linear equations over \(\mathbb{Z}_2\):
Test expectations:
Measuring the first register yields an \(n\)-bit string \(y\) such that
which means that the quantum subroutine does not directly output \(b\) and provides a linear constraint on \(b\) instead.
If b=0 (the one-to-one case), \(y\) is uniformly random over all \(n\)-bit strings. Otherwise, \(y\) is uniformly distributed over the subspace orthogonal to \(b\).
Doc references: [22]
API#
qolumbina.programs.hidden_subgroup_problem.hidden_shift#
Hidden Shift Benchmark Program - Qiskit Kernel (C) Quantum Economic Development Consortium (QED-C) 2024.
- class HiddenShift(hidden_bits, if_barrier=True, name=None)[source]#
Bases:
QuantumCircuit- Parameters:
hidden_bits (list[int]) – List of bits representing the hidden shift, i.e., \([s_0, s_1, \dots, s_{n-1}]\).
if_barrier (bool) – Whether to include barriers in the circuit. Defaults to
True.name (str | None) – Name of the circuit. Defaults to
None.
- Raises:
ValueError – If the length of
hidden_bitsis not even, as the bent function used in this benchmark is only achievable for even number of qubits.
qolumbina.programs.hidden_subgroup_problem.simon#
Simon’s algorithm.
- class Simon(b, if_barrier=True, name=None)[source]#
Bases:
QuantumCircuitSimon’s algorithm circuit.
Finds the hidden bitstring b for a function f such that f(x) = f(y) iff x = y or x = y xor b, where xor is bitwise XOR. This circuit implements the quantum part of Simon’s algorithm, which finds bitstrings y such that b . y = 0 (mod 2). The full algorithm requires classical postprocessing to find b from these bitstrings.
- Parameters:
b (str) – The hidden bitstring \(b\).
if_barrier (bool) – Whether to include barriers in the circuit.
name (str | None) – Optional name for the circuit.
- Raises:
ValueError – If b is not a valid bitstring with elements ‘0’ and ‘1’.