Algorithms

`trueq.algorithms.algorithms.bernstein_vazirani`	Returns a circuit which implements the Bernstein-Vazirani algorithm for finding a hidden bitstring \(s \in \{0, 1\}^n\) that defines a function \(f: \{0, 1\}^n \rightarrow\{0, 1\}\) via \(f(x) = x_1 s_1 \oplus \dots \oplus x_n s_n\).
`trueq.algorithms.algorithms.simon`	Returns a circuit which implements Simon's algorithm for a periodic function \(f: \{0, 1\}^n \rightarrow \{0, 1\}^n\) specified by the period \(s \in \{0, 1\}^n\) via \(f(x) = x \oplus x_i s\), where \(i\) is the smallest index for which \(s_i = 1\).
`trueq.algorithms.subroutines.qft`	Returns a circuit which implements the quantum Fourier transform on \(n\)-qubits, \(\mathcal{F}_{2^n}\).

Algorithms

trueq.algorithms.algorithms.bernstein_vazirani(bitstring)

Returns a circuit which implements the Bernstein-Vazirani algorithm for finding a hidden bitstring \(s \in \{0, 1\}^n\) that defines a function \(f: \{0, 1\}^n \rightarrow\{0, 1\}\) via \(f(x) = x_1 s_1 \oplus \dots \oplus x_n s_n\). Classically one needs to evaluate the function \(f\) at least \(\Omega(n)\) times to achieve this task, whereas this quantum algorithm requires a single application of a unitary circuit satisfying \(U_f |x \rangle |b\rangle = |x \rangle |b\oplus f(x) \rangle\) for all \(x \in \{0,1\}^n\) and \(b \in \{0,1\}\).

import trueq as tq
import numpy as np

circuit = tq.algorithms.bernstein_vazirani((1, 1, 1, 1, 1))
circuit.draw()

# simulate the circuit and plot the output distribution
tq.Simulator().sample(circuit, n_shots=np.inf).plot()

Parameters:: bitstring (tuple) – The bitstring that defines the function \(f\).
Return type:: Circuit

trueq.algorithms.algorithms.simon(period)

Returns a circuit which implements Simon’s algorithm for a periodic function \(f: \{0, 1\}^n \rightarrow \{0, 1\}^n\) specified by the period \(s \in \{0, 1\}^n\) via \(f(x) = x \oplus x_i s\), where \(i\) is the smallest index for which \(s_i = 1\).

Simon’s problem is to find the (hidden) period \(s\) given oracle access to a function \(f\) that satisfies the periodicity property: \(f(x) = f(y)\) if and only if \(x = y\) or \(x = y \oplus s\). Every probabilistic classical algorithm that solves this problem requires at least \(\Omega(2^{n/2})\) evaluations of the function \(f\), whereas Simon’s algorithm requires only \(O(n)\) calls to a unitary satisfying \(U_f |x \rangle |y\rangle = |x \rangle |y\oplus f(x) \rangle\).

The circuit uses \(n-1\) auxiliary qubits, and maps the \(n\)-qubit data register to a uniform superposition of all computational basis states \(|x\rangle\) that satisfy \(x_1 s_1 \oplus \dots \oplus x_n s_n = 0\). To compute the period \(s\) on the quantum computer, one draws \(O(n)\) samples from the output state, then uses classical processing to find \(s\) by solving a system of binary linear constraints.

import trueq as tq
import numpy as np

circuit = tq.algorithms.simon((1, 1, 1, 1, 1))
circuit.draw()

# simulate the circuit and plot the output distribution
tq.Simulator().sample(circuit, n_shots=np.inf).plot()

Parameters:: period (tuple) – The period of the implictly defined function \(f\).
Return type:: Circuit

Subroutines

trueq.algorithms.subroutines.qft(labels, truncate_at=None, swap=True)

Returns a circuit which implements the quantum Fourier transform on \(n\)-qubits, \(\mathcal{F}_{2^n}\).

By default, the returned circuit contains no approximations. However, by calling this method with an integer value for truncate_at, the returned circuit will be approximated by truncating certain controlled-\(Z\) rotations. Given an integer \(b\), the approximated Fourier transform will not contain controlled-\(Z\) rotations with angles smaller than \(2 \pi / 2^{b+1}\), or in other words, all cascades of controlled rotations will have depth no longer than \(b\).

Setting swap to False omits the final subcircuit which reverses the order of the qubits. This step requires \(O(n)\) swap gates, and can be safely omitted and replaced by classical post-processing if the QFT is immediately followed by measurement.

import numpy as np
import trueq as tq

circuit = tq.algorithms.qft(range(4), truncate_at=2)
circuit.measure_all()
circuit.draw()

Parameters:

labels (Iterable) – The qubit labels on which the Fourier transform acts.
truncate_at (NoneType | int) – An integer \(b\), which specifies the removal of all controlled-\(Z\) gates with an angle smaller than \(2 \pi / 2^b\), or None by default to remove no gates in the generated circuit.
swap (bool) – Whether to include the subcircuit which reverses the order of the qubits at the end of the QFT circuit. Default is True.

Return type:

Circuit