Algorithms#

Qibo provides circuit constructions of quantum algorithms. They are implemented in qibo/models/algorithms, and all of them are available from qibo.models, e.g. from qibo.models import QFT.

Fourier transform and phase estimation#

Quantum Fourier Transform (QFT)#

class qibo.models.QFT(nqubits, with_swaps=True, accelerators=None, **kwargs)[source]#

Creates a circuit that implements the Quantum Fourier Transform.

The Quantum Fourier Transform (QFT) on \(n\) qubits is the unitary operator that acts on the computational basis states as

\[\text{QFT} \, \ket{j} = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2 \pi i j k / N} \ket{k} \, ,\]

where \(N = 2^{n}\), i.e. it applies the discrete Fourier transform to the amplitudes of a state. The integer \(j = j_{1} 2^{n - 1} + \cdots + j_{n} 2^{0}\) is represented by the bitstring \(j_{1} \cdots j_{n}\) of the qubits, with the first qubit being the most significant one. The circuit is the one in Fig. 5.1 of Ref. [1]. For each qubit \(q = 0, \dots, n - 1\), from the first to the last, it applies

  1. a Hadamard gate on the qubit \(q\);

  2. the controlled-\(R_{k}\) gates, implemented with qibo.gates.CU1, that have the qubit \(q + k - 1\) as control and the qubit \(q\) as target, for \(k = 2, \dots, n - q\), where

    \[\begin{split}R_{k} = \begin{pmatrix} 1 & 0 \\ 0 & e^{2 \pi i / 2^{k}} \end{pmatrix} \, .\end{split}\]

If with_swaps=True, \(\lfloor n / 2 \rfloor\) qibo.gates.SWAP gates are added at the end to reverse the order of the qubits. Hence, the circuit has \(n (n + 1) / 2\) Hadamard and controlled phase gates, plus the swaps, which is \(\Theta(n^{2})\) gates. The inverse QFT is obtained with qibo.models.circuit.Circuit.invert().

Example

import numpy as np

from qibo.backends import NumpyBackend
from qibo.models import QFT
from qibo.quantum_info import random_statevector

backend = NumpyBackend()

nqubits = 6
dims = 2**nqubits

# Random normalized initial state vector
initial_state = random_statevector(dims, backend=backend)

circuit = QFT(nqubits)

# Execute the circuit
final_state = circuit(initial_state)
Parameters:

  • nqubits (int) – number of qubits in the circuit.

  • with_swaps (bool, optional) – If True, uses qibo.gates.SWAP gates at the end of the circuit so that the qubit order in the final state is the same as the initial state. Otherwise, the qubits of the final state are in the reverse order. Defaults to True.

  • accelerators (dict, optional) – Accelerator device dictionary in order to use a distributed circuit. If None, a simple (non-distributed) circuit will be used.

  • kwargs (dict, optional) – Additional arguments used to initialize qibo.models.Circuit. For details, see the documentation of qibo.models.circuit.Circuit.

Returns:

implementation of the Quantum Fourier Transform.

Return type:

qibo.models.Circuit

References

1. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2010), Sec. 5.1.

Quantum Phase Estimation (QPE)#

qibo.models.QPE(unitary, nqubits_counting, measure=True, **kwargs)[source]#

Creates a circuit that implements the canonical Quantum Phase Estimation.

Given a unitary \(U\) and one of its eigenstates \(|\psi\rangle\), such that \(U|\psi\rangle = e^{2 \pi i \varphi}|\psi\rangle\), the circuit estimates \(\varphi \in [0, \, 1)\) with \(t\) bits of precision, where \(t\) is the number of counting qubits. It acts on \(t + n\) qubits, with \(n\) being the number of qubits of \(U\), and it is composed of the following steps:

  1. a Hadamard gate on each of the \(t\) counting qubits, which are the first qubits of the circuit;

  2. \(U^{2^{t - 1 - j}}\), controlled by the counting qubit \(j\), acting on the last \(n\) qubits of the circuit, the target qubits;

  3. the inverse qibo.models.QFT on the counting qubits;

  4. the measurement of the counting qubits, if measure=True.

The target qubits have to be prepared in \(|\psi\rangle\) before the circuit is applied, e.g. by adding the circuit that prepares it to a larger circuit before the one returned by this function. At the end, the counting qubits hold a bitstring \(b_{1} \cdots b_{t}\), with \(b_{1}\) being the outcome of the first qubit, such that \(\varphi\) is approximated by \(0.b_{1} \cdots b_{t}\) in binary, which is exact if \(\varphi\) is an integer multiple of \(2^{-t}\). The conversion from the bitstring into the phase can be done with qibo.quantum_info.bitstring_to_phase(), and the phase of the most probable outcome, i.e. the estimate of \(\varphi\), with qibo.quantum_info.estimate_phase().

Note

The power \(U^{2^{k}}\) is implemented by applying the controlled \(U\) a number \(2^{k}\) of times. Hence, \(U\) is applied \(2^{t} - 1\) times in total.

Parameters:

  • unitary (qibo.models.circuit.Circuit or qibo.gates.Gate or ndarray) – unitary \(U\), given as a circuit, as a gate, e.g. qibo.gates.Unitary, or as a matrix. A matrix must be unitary and of dimension \(2^{n} \times 2^{n}\) with \(n > 0\), and it is converted into a qibo.gates.Unitary acting on \(n\) qubits. The qubits of a gate are relabeled, in increasing order, as the qubits of a circuit with the same number of qubits as the gate. All of the gates must be supported by qibo.models.circuit.Circuit.controlled_by().

  • nqubits_counting (int) – number of counting qubits \(t\). The phase is estimated with a resolution of \(2^{-t}\).

  • measure (bool, optional) – If True, adds a measurement of the counting qubits at the end of the circuit. Defaults to True.

  • kwargs (dict, optional) – Additional arguments used to initialize qibo.models.circuit.Circuit. For details, see the documentation of qibo.models.circuit.Circuit.

Returns:

implementation of the Quantum Phase Estimation.

Return type:

qibo.models.circuit.Circuit

Example

import math

from qibo import Circuit, gates
from qibo.models import QPE
from qibo.quantum_info import estimate_phase

# unitary with eigenstate |1> and eigenvalue exp(2 pi i phase)
phase = 5 / 16
unitary = Circuit(1)
unitary.add(gates.U1(0, theta=2 * math.pi * phase))

# phase estimation with 4 counting qubits
nqubits_counting = 4
qpe = QPE(unitary, nqubits_counting)

# prepare the eigenstate in the target qubit and apply the phase estimation
circuit = Circuit(qpe.nqubits)
circuit.add(gates.X(nqubits_counting))
circuit.add(qpe)

result = circuit(nshots=100)
print(estimate_phase(result))

0.3125

References

1. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited, Proc. R. Soc. Lond. A 454, 339 (1998).

2. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2010), Sec. 5.2.

Iterative Quantum Phase Estimation (IQPE)#

qibo.models.IQPE(unitary, nbits, **kwargs)[source]#

Creates a circuit that implements the Iterative Quantum Phase Estimation.

Given a unitary \(U\) and one of its eigenstates \(|\psi\rangle\), such that \(U|\psi\rangle = e^{2 \pi i \varphi}|\psi\rangle\), the circuit estimates \(\varphi \in [0, \, 1)\) with \(t\) bits of precision, where \(t\) is nbits, as qibo.models.QPE() does. However, a single counting qubit is measured \(t\) times, instead of using \(t\) counting qubits and the inverse qibo.models.QFT. The circuit acts on \(1 + n\) qubits, with \(n\) being the number of qubits of \(U\). The first qubit is the counting qubit and the last \(n\) qubits are the target qubits.

The bits of \(\varphi\) are obtained one at a time, starting from the least significant one. In each step \(k = 1, \dots, t\):

  1. a Hadamard gate is applied to the counting qubit;

  2. \(U^{2^{t - k}}\) is applied to the target qubits, controlled by the counting qubit;

  3. a phase gate is applied to the counting qubit, with the angle \(-2 \pi \sum_{j=1}^{k-1} m_{j} \, 2^{-(k - j + 1)}\), where \(m_{j}\) is the outcome of the step \(j\), which removes the contribution of the bits that were already measured;

  4. a Hadamard gate is applied to the counting qubit, which is measured with collapse=True, and the outcome \(m_{k}\) is the bit \(b_{t - k + 1}\) of \(\varphi = 0.b_{1} \cdots b_{t}\);

  5. if it is not the last step, the counting qubit is reset to \(|0\rangle\) with an \(X\) rotation conditioned on \(m_{k}\).

The circuit finishes with a measurement of the counting qubit that is not collapsed, so that it can be simulated with state vectors. The target qubits have to be prepared in \(|\psi\rangle\) before the circuit is applied, e.g. by adding the circuit that prepares it to a larger circuit before the one returned by this function.

The outcomes of the measurements are not merged into the result of the execution of the circuit. They are returned as a list of qibo.measurements.MeasurementResult, which is ordered from the most to the least significant bit, i.e. in the reverse order of the measurements. Hence, they can be joined with qibo.measurements.MeasurementResult.join() and the estimate of \(\varphi\) is obtained with qibo.quantum_info.estimate_phase().

Note

As in qibo.models.QPE(), \(U\) is applied \(2^{t} - 1\) times in total. The circuit has fewer qubits, but when it is simulated, each shot has to be simulated separately because of the measurements with collapse.

Example

import math

from qibo import Circuit, gates
from qibo.measurements import MeasurementResult
from qibo.models import IQPE
from qibo.quantum_info import estimate_phase

# unitary with eigenstate |1> and eigenvalue exp(2 pi i phase)
phase = 5 / 16
unitary = Circuit(1)
unitary.add(gates.U1(0, theta=2 * math.pi * phase))

# phase estimation with 4 bits
iqpe, results = IQPE(unitary, 4)

# prepare the eigenstate in the target qubit and apply the phase estimation
circuit = Circuit(iqpe.nqubits)
circuit.add(gates.X(1))
circuit.add(iqpe)
circuit(nshots=100)

print(estimate_phase(MeasurementResult.join(*results)))

0.3125
Parameters:
Returns:

the circuit that implements the Iterative Quantum Phase Estimation and the list of qibo.measurements.MeasurementResult with the outcomes of the measurements of the counting qubit, from the most to the least significant bit.

Return type:

tuple

References

1. A. Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem, arXiv:quant-ph/9511026.

2. R. B. Griffiths and C.-S. Niu, Semiclassical Fourier Transform for Quantum Computation, Phys. Rev. Lett. 76, 3228 (1996).

Amplitude estimation#

Quantum Amplitude Estimation (QAE)#

qibo.models.QAE(algorithm, oracle, nqubits_counting, measure=True, **kwargs)[source]#

Creates a circuit that implements the canonical Quantum Amplitude Estimation.

Given a circuit \(\mathcal{A}\), which prepares the state \(|\Psi\rangle = \mathcal{A}|0\rangle\) from the all-zero state \(|0\rangle\), and an oracle that marks the “good” computational basis states, the circuit estimates the probability \(a = \sin^{2}(\theta_{a})\) of measuring a good state in \(|\Psi\rangle\), where \(\theta_{a} \in [0, \, \pi / 2]\). It acts on \(t + n\) qubits, with \(t\) being the number of counting qubits and \(n\) the number of qubits of \(\mathcal{A}\), and it is composed of the following steps:

  1. \(\mathcal{A}\) on the last \(n\) qubits of the circuit;

  2. the qibo.models.QPE() of the amplification operator \(\mathbf{Q}\) of qibo.models.amplification_operator(), with the \(t\) first qubits as counting qubits.

The state \(|\Psi\rangle\) is a superposition of two eigenvectors of \(\mathbf{Q}\), with eigenvalues \(e^{\pm 2 i \theta_{a}}\). Hence, if \(y\) is the integer represented by the bitstring of the counting qubits, and \(M = 2^{t}\), then \(y / M\) approximates \(\theta_{a} / \pi\) or \(1 - \theta_{a} / \pi\), and the estimate of \(a\) is \(\tilde{a} = \sin^{2}(\pi y / M)\). The phase \(y / M\) of the most probable outcome is given by qibo.quantum_info.estimate_phase(). With probability of at least \(8 / \pi^{2}\),

\[|\tilde{a} - a| \leq \frac{2 \pi \sqrt{a (1 - a)}}{M} + \frac{\pi^{2}}{M^{2}} \, .\]

Note

\(\mathbf{Q}\) is applied \(2^{t} - 1\) times in total.

Example

import math

from qibo import Circuit, gates
from qibo.models import QAE
from qibo.quantum_info import estimate_phase

# state cos(theta) |0> + sin(theta) |1> with theta = pi / 8, and good state |1>
theta = math.pi / 8
algorithm = Circuit(1)
algorithm.add(gates.RY(0, theta=2 * theta))
oracle = Circuit(1)
oracle.add(gates.Z(0))

# amplitude estimation with 3 counting qubits
circuit = QAE(algorithm, oracle, 3)
result = circuit(nshots=100)

print(round(math.sin(math.pi * estimate_phase(result)) ** 2, 4))

0.1464
Parameters:

  • algorithm (qibo.models.circuit.Circuit) – circuit \(\mathcal{A}\). It cannot contain measurements.

  • oracle (qibo.models.circuit.Circuit) – circuit that multiplies the good states by \(-1\), e.g. a multi-controlled qibo.gates.Z gate. It must act on the same number of qubits as algorithm, and it cannot contain measurements.

  • nqubits_counting (int) – number of counting qubits \(t\), which sets the resolution \(2^{-t}\) of the estimate of \(\theta_{a} / \pi\).

  • measure (bool, optional) – If True, adds a measurement of the counting qubits at the end of the circuit. Defaults to True.

  • kwargs (dict, optional) – Additional arguments used to initialize qibo.models.circuit.Circuit, e.g. density_matrix=True. For details, see the documentation of qibo.models.circuit.Circuit.

Returns:

implementation of the Quantum Amplitude Estimation.

Return type:

qibo.models.circuit.Circuit

References

1. G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum Amplitude Amplification and Estimation, Contemporary Mathematics 305, 53 (2002).

2. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited, Proc. R. Soc. Lond. A 454, 339 (1998).

Quantum Counting#

qibo.models.Counting(oracle, nqubits_counting, measure=True, **kwargs)[source]#

Creates a circuit that implements the Quantum Counting algorithm.

Given a Boolean function \(\chi\) over the \(N = 2^{n}\) computational basis states of \(n\) qubits, the circuit estimates the number \(M\) of states that \(\chi\) marks with \(1\). It is the qibo.models.QAE() of the uniform superposition of the \(N\) states, i.e. with Hadamard gates on every qubit as the circuit that prepares the state, in which the probability of measuring a marked state is \(M / N = \sin^{2}(\theta)\). The circuit acts on \(t + n\) qubits, with \(t\) being the number of counting qubits. If \(y\) is the integer represented by the bitstring of the counting qubits, and \(L = 2^{t}\), then the estimate of \(M\) is

\[\tilde{M} = N \sin^{2}\left( \frac{\pi y}{L} \right) \, .\]

The phase \(y / L\) of the most probable outcome is given by qibo.quantum_info.estimate_phase(). With probability of at least \(8 / \pi^{2}\),

\[|\tilde{M} - M| \leq \frac{2 \pi \sqrt{M (N - M)}}{L} + \frac{\pi^{2} N}{L^{2}} \, .\]

For \(M = 0\), the estimate is exact, which decides if there are any marked states.

Example

import math

from qibo import Circuit, gates
from qibo.models import Counting
from qibo.quantum_info import estimate_phase

# oracle that marks the states 10 and 11 of 2 qubits
oracle = Circuit(2)
oracle.add(gates.Z(0))

# counting with 3 counting qubits
circuit = Counting(oracle, 3)
result = circuit(nshots=100)

print(round(4 * math.sin(math.pi * estimate_phase(result)) ** 2))

2
Parameters:

  • oracle (qibo.models.circuit.Circuit) – circuit that multiplies the marked states by \(-1\), e.g. a multi-controlled qibo.gates.Z gate. It cannot contain measurements.

  • nqubits_counting (int) – number of counting qubits \(t\), which sets the resolution \(2^{-t}\) of the estimate of \(\theta / \pi\).

  • measure (bool, optional) – If True, adds a measurement of the counting qubits at the end of the circuit. Defaults to True.

  • kwargs (dict, optional) – Additional arguments used to initialize qibo.models.circuit.Circuit, e.g. density_matrix=True. For details, see the documentation of qibo.models.circuit.Circuit.

Returns:

implementation of the Quantum Counting.

Return type:

qibo.models.circuit.Circuit

References

1. G. Brassard, P. Høyer, and A. Tapp, Quantum Counting, Automata, Languages and Programming, LNCS 1443, 820 (1998).

2. G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum Amplitude Amplification and Estimation, Contemporary Mathematics 305, 53 (2002).

Maximum-likelihood Quantum Amplitude Estimation (MLQAE)#

qibo.models.MLQAE(algorithm, oracle, check, nlevels=5, nshots=100, backend=None)[source]#

Estimates an amplitude with the Maximum-likelihood Quantum Amplitude Estimation.

Let \(a\) be the probability of measuring a good state in \(\mathcal{A}|0\rangle\), where \(\mathcal{A}\) is the circuit algorithm, \(|0\rangle\) is the all-zero state, and the good states are marked by the oracle. Let \(\theta_{a} \in [0, \, \pi / 2]\) be such that \(a = \sin^{2}(\theta_{a})\). After \(m\) applications of the operator \(\mathbf{Q}\) of qibo.models.amplification_operator(), the probability of measuring a good state is \(\sin^{2}((2m + 1)\theta_{a})\). Differently from qibo.models.QAE(), there are no counting qubits nor controlled operations. Instead, the circuit \(\mathbf{Q}^{m}\mathcal{A}\) is measured nshots times for each \(m\) in \(\{0, \, 1, \, 2, \, 4, \, \dots, \, 2^{L - 1}\}\), where \(L\) is nlevels. If \(h_{m}\) of the outcomes are good for a given \(m\), the estimate is \(\sin^{2}(\hat{\theta})\), where \(\hat{\theta}\) maximizes the likelihood

\[\prod_{m} \sin^{2}\left((2m + 1)\theta\right)^{h_{m}} \, \cos^{2}\left((2m + 1)\theta\right)^{N - h_{m}} \, ,\]

with \(N\) being nshots. The maximum is found with a grid search on \([0, \, \pi / 2]\), which is refined around the best point. The number of applications of \(\mathcal{A}\) and \(\mathcal{A}^{-1}\) is \(N \sum_{m} (2m + 1)\). With this exponential schedule of \(m\), the error is reported to approach the Heisenberg limit, which is inversely proportional to that number (Ref. [1]).

Example

import math

from qibo import Circuit, gates
from qibo.models import MLQAE

# state cos(theta) |0> + sin(theta) |1> with theta = 0.5, and good state |1>
algorithm = Circuit(1)
algorithm.add(gates.RY(0, theta=2 * 0.5))
oracle = Circuit(1)
oracle.add(gates.Z(0))

estimate = MLQAE(algorithm, oracle, check=lambda bitstring: bitstring == "1")

# the exact amplitude is sin(0.5)^2, which is approximately 0.23
print(round(estimate, 1))

0.2
Parameters:

  • algorithm (qibo.models.circuit.Circuit) – circuit \(\mathcal{A}\) without measurements.

  • oracle (qibo.models.circuit.Circuit) – circuit \(\mathbf{S}_{\chi}\) that multiplies the good states by \(-1\), without measurements and with the same number of qubits as algorithm. See qibo.models.amplification_operator().

  • check (Callable) – function that receives a measured bitstring, e.g. "101", and returns True if the state is good.

  • nlevels (int, optional) – number \(L\) of levels of the schedule of the numbers of iterations, which are \(0\) and \(2^{k}\), for \(k = 0, \dots, L - 1\). Defaults to \(5\).

  • nshots (int, optional) – number of shots of each circuit. Defaults to \(100\).

  • backend (qibo.backends.abstract.Backend, optional) – backend to be used in the execution of the circuits and in the maximization. If None, it uses the current backend. Defaults to None.

Returns:

estimate of \(a\), which belongs to the interval \([0, \, 1]\).

Return type:

float

References

1. Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, Amplitude estimation without phase estimation, Quantum Inf. Process. 19, 75 (2020).

2. G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum Amplitude Amplification and Estimation, Contemporary Mathematics 305, 53 (2002).

Iterative Quantum Amplitude Estimation (IQAE)#

class qibo.models.IQAE(circuit_a, circuit_q, alpha=0.05, epsilon=0.005, n_shots=1024, method='chernoff')[source]#

Iterative Quantum Amplitude Estimation (IQAE).

Let \(\mathcal{A}\) be a circuit on \(n + 1\) qubits, such that

\[\mathcal{A} \ket{0}_{n} \ket{0} = \sqrt{1 - a} \, \ket{\psi_{0}}_{n} \ket{0} + \sqrt{a} \, \ket{\psi_{1}}_{n} \ket{1},\]

where \(\ket{\psi_{0}}_{n}\) and \(\ket{\psi_{1}}_{n}\) are normalized states and \(a \in [0, 1]\) is the unknown probability of measuring the last qubit in the state \(\ket{1}\). Let \(\mathbf{Q}\) be the operator of qibo.models.amplification_operator() for \(\mathcal{A}\) and for the oracle that multiplies by \(-1\) the states with the last qubit in the state \(\ket{1}\), e.g. a qibo.gates.Z gate on the last qubit. For \(a = \sin^{2}(\theta_{a})\) and any integer \(k \geq 0\),

\[\mathbf{Q}^{k} \mathcal{A} \ket{0}_{n} \ket{0} = \cos((2k + 1) \theta_{a}) \ket{\psi_{0}}_{n} \ket{0} + \sin((2k + 1) \theta_{a}) \ket{\psi_{1}}_{n} \ket{1},\]

so the probability of measuring the last qubit in the state \(\ket{1}\) is \(\sin^{2}((2k + 1) \theta_{a})\). In contrast with qibo.models.QAE(), IQAE does not use quantum phase estimation, hence it needs neither counting qubits nor controlled powers of \(\mathbf{Q}\). It only applies \(\mathbf{Q}\) to \(\mathcal{A}\ket{0}\) and measures the last qubit. Starting from the interval \([\theta_{l}, \theta_{u}] = [0, \pi / 2]\) for \(\theta_{a}\), each iteration \(i\)

  1. finds the largest power \(k_{i}\) such that \(K_{i} = 4 k_{i} + 2 \geq 2 K_{i-1}\) and the interval \(K_{i} [\theta_{l}, \theta_{u}]\), modulo \(2 \pi\), lies completely in \([0, \pi]\) or in \([\pi, 2 \pi]\). If there is none, it keeps \(k_{i-1}\);

  2. measures the last qubit of \(\mathbf{Q}^{k_{i}} \mathcal{A} \ket{0}\) n_shots times, or fewer times in the last iterations, where more shots would not improve the result (the “no-overshooting” condition). With all of the shots of the iterations that share \(k_{i}\), it computes a confidence interval of \(\sin^{2}((2 k_{i} + 1) \theta_{a}) = (1 - \cos(K_{i} \theta_{a})) / 2\);

  3. inverts the cosine, which is unambiguous in each half of the circle, and shrinks \([\theta_{l}, \theta_{u}]\).

The algorithm stops when \(\theta_{u} - \theta_{l} \leq 2 \epsilon\), where \(\epsilon\) is epsilon, and it returns the interval \([a_{l}, a_{u}] = [\sin^{2}(\theta_{l}), \sin^{2}(\theta_{u})]\). The significance level of each confidence interval is the one of the algorithm, \(\alpha\), divided by the maximum number \(\lceil \log_{2}(\pi / (8 \epsilon)) \rceil\) of rounds, a round being the set of iterations with the same \(k_{i}\). Then, \(a_{u} - a_{l} \leq 2 \epsilon\) and \(a\) lies in \([a_{l}, a_{u}]\) with probability at least \(1 - \alpha\). Thus, the estimation \((a_{l} + a_{u}) / 2\) differs from \(a\) by at most \(\epsilon\) with that probability. If n_shots is not larger than

\[N_{\max}(\epsilon, \alpha) = \left\lceil \frac{32}{(1 - 2 \sin(\pi / 14))^{2}} \log\left(\frac{2}{\alpha} \log_{2}\left(\frac{\pi}{4 \epsilon}\right)\right) \right\rceil,\]

the algorithm ends after at most \(\lceil \log_{2}(\pi / (8 \epsilon)) \rceil\) rounds and \(\mathbf{Q}\) is applied fewer than \((50 / \epsilon) \log((2 / \alpha) \log_{2}(\pi / (4 \epsilon)))\) times. This is the quadratic speedup over the \(O(1 / \epsilon^{2})\) samples of classical Monte Carlo simulation, up to a double-logarithmic factor.

Note

For the default values of epsilon and alpha, \(N_{\max} = 590\), which is smaller than the default n_shots.

The circuit circuit_q can act on more qubits than circuit_a, e.g. on auxiliary qubits, as long as it leaves them in the state \(\ket{0}\).

Example

import math

from qibo import Circuit, gates
from qibo.models import IQAE, amplification_operator

# A applies a Hadamard gate on the first qubit and, if it is in the state 1, a
# rotation of angle 2 on the last qubit, so a = sin(1)^2 / 2
algorithm = Circuit(2)
algorithm.add(gates.H(0))
algorithm.add(gates.CRY(0, 1, theta=2.0))

# the oracle multiplies by -1 the states with the last qubit in the state 1
oracle = Circuit(2)
oracle.add(gates.Z(1))
operator = amplification_operator(algorithm, oracle)

iqae = IQAE(algorithm, operator, alpha=0.05, epsilon=0.01)
result = iqae.execute()

print(abs(result.estimation - math.sin(1.0) ** 2 / 2) <= 0.01)

True
Parameters:

  • circuit_a (qibo.models.circuit.Circuit) – circuit \(\mathcal{A}\) without measurements. Its last qubit is the one that is measured.

  • circuit_q (qibo.models.circuit.Circuit) – circuit of the operator \(\mathbf{Q}\), which has to act on at least as many qubits as circuit_a.

  • alpha (float, optional) – significance level \(\alpha \in (0, 1)\), i.e. the probability that the interval returned does not contain \(a\) is at most alpha. Defaults to \(0.05\).

  • epsilon (float, optional) – target accuracy \(\epsilon \in (0, 0.5]\) of the estimation of \(a\). Defaults to \(0.005\).

  • n_shots (int, optional) – number of shots of each iteration. Defaults to \(1024\).

  • method (str, optional) – method used to compute the confidence intervals of each iteration, either "chernoff" for the Chernoff-Hoeffding intervals or "beta" for the Clopper-Pearson intervals. Defaults to "chernoff".

References

1. D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, Iterative quantum amplitude estimation, npj Quantum Inf. 7, 52 (2021), arXiv:1912.05559.

2. G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum Amplitude Amplification and Estimation, Contemporary Mathematics 305, 53 (2002).

3. C. J. Clopper and E. S. Pearson, The use of confidence or fiducial limits illustrated in the case of the binomial, Biometrika 26, 404 (1934).

4. W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc. 58, 13 (1963).

construct_qae_circuit(k)[source]#

Creates the circuit that applies \(\mathbf{Q}^{k}\) to \(\mathcal{A}\ket{0}\) and measures the last qubit of circuit_a.

Parameters:

k (int) – number \(k \geq 0\) of applications of circuit_q.

Returns:

circuit with as many qubits as circuit_q.

Return type:

qibo.models.circuit.Circuit

clopper_pearson(count, n, alpha)[source]#

Calculates the Clopper-Pearson confidence interval of the probability \(a\).

Parameters:

  • count (int) – number of successes, i.e. of measurements of the state \(\ket{1}\).

  • n (int) – total number of trials.

  • alpha (float) – significance level, i.e. the probability that the interval does not contain \(a\) is at most alpha.

Returns:

lower and upper bounds of the interval. A bound that cannot be computed, which happens if count is \(0\) or n, is replaced by \(0\) or \(1\).

Return type:

tuple

h_calc_CP(n_successes, n_total_shots, upper_bound_t)[source]#

Calculates half of the width of the Clopper-Pearson interval of \(K \theta_{a}\).

The Clopper-Pearson interval \([a_{\min}, a_{\max}]\) of the probability \(a\) has significance level alpha / upper_bound_t, and the result is \(|\arccos(1 - 2 a_{\max}) - \arccos(1 - 2 a_{\min})| / 2\).

Parameters:

  • n_successes (int) – number of successes.

  • n_total_shots (int) – total number of trials.

  • upper_bound_t (int) – maximum number \(T\) of rounds needed to achieve the target accuracy.

Returns:

half of the width of the interval of \(K \theta_{a}\), in radians.

Return type:

float

calc_L_range_CP(n_shots, upper_bound_t)[source]#

Calculates the maximum and minimum errors of an iteration with Clopper-Pearson intervals.

They are the maximum and the minimum of h_calc_CP() over the fractions of successes in \([0, 1]\), divided by \(2 \pi\). The maximum is the quantity \(L_{\max}\) of the no-overshooting condition.

Parameters:

  • n_shots (int) – number of shots.

  • upper_bound_t (int) – maximum number \(T\) of rounds needed to achieve the target accuracy.

Returns:

maximum and minimum errors that an iteration can return, in units of \(2 \pi\).

Return type:

tuple

calc_L_range_CH(n_shots, upper_bound_t)[source]#

Calculates the maximum and minimum errors of an iteration, with Chernoff-Hoeffding.

The maximum error is

\[L_{\max} = \frac{1}{2 \pi} \arcsin\left(\left(\frac{2}{N_{shots}} \log\left(\frac{2 T}{\alpha}\right)\right)^{1 / 4}\right),\]

which is used in the no-overshooting condition.

Parameters:

  • n_shots (int) – number of shots \(N_{shots}\).

  • upper_bound_t (int) – maximum number \(T\) of rounds needed to achieve the target accuracy.

Returns:

maximum error, in units of \(2 \pi\), and a lower value that is not used by execute().

Return type:

tuple

find_next_k(uppercase_k_i, up_i, theta_l, theta_u, r=2)[source]#

Finds the next factor \(K\), which is the procedure FindNextK of [1].

It is the largest \(K = 4k + 2 \geq r K_{i}\) such that the interval \(K [\theta_{l}, \theta_{u}]\) lies completely in \([0, \pi]\) or in \([\pi, 2 \pi]\), modulo \(2 \pi\). All of the angles are divided by \(2 \pi\).

Parameters:

  • uppercase_k_i (int) – current factor \(K_{i} = 4 k_{i} + 2\), where \(k_{i}\) is the power of circuit_q.

  • up_i (bool) – whether the current interval of \(K_{i} \theta_{a}\) lies in the upper half of the circle, \([0, \pi]\), or in the lower one.

  • theta_l (float) – lower limit of the current interval of \(\theta_{a}\).

  • theta_u (float) – upper limit of the current interval of \(\theta_{a}\).

  • r (int, optional) – minimum ratio \(K / K_{i}\). Defaults to \(2\).

Returns:

next factor \(K = 4k + 2\), and whether the extrapolated interval lies in the upper half of the circle. If there is no valid \(K\), it returns uppercase_k_i and up_i.

Return type:

tuple

execute(backend=None)[source]#

Executes the IQAE algorithm.

Parameters:

backend (qibo.backends.abstract.Backend, optional) – backend used to execute the circuits. If None, it uses the current backend. Defaults to None.

Returns:

result with the estimation of \(a\), its interval and the information of each iteration.

Return type:

qibo.models.IterativeAmplitudeEstimationResult

class qibo.models.IterativeAmplitudeEstimationResult[source]#

Result of qibo.models.IQAE.execute().

alpha#

significance level \(\alpha\).

Type:

float

epsilon_target#

target accuracy \(\epsilon\).

Type:

float

epsilon_estimated#

estimated accuracy, i.e. half of the width \((a_{u} - a_{l}) / 2\) of the final interval.

Type:

float

estimation#

estimation \((a_{l} + a_{u}) / 2\) of \(a\).

Type:

float

estimate_intervals#

initial bounds \(0\) and \(1\) of \(a\), followed by the interval \([a_{l}, a_{u}]\) after each iteration.

Type:

list

theta_intervals#

initial bounds \(0\) and \(1 / 4\) of \(\theta_{a} / (2 \pi)\), followed by the interval \([\theta_{l}, \theta_{u}] / (2 \pi)\) after each iteration.

Type:

list

num_oracle_queries#

total number of applications of circuit_q.

Type:

int

k_list#

power of circuit_q, starting with \(k_{0} = 0\) and followed by the one of each iteration.

Type:

list

ratios#

number of times that the state \(\ket{1}\) was measured in each iteration.

Type:

list

shots#

number of shots of each iteration.

Type:

list

Oracle algorithms#

Deutsch-Jozsa#

qibo.models.DeutschJozsa(oracle, measure=True, **kwargs)[source]#

Creates a circuit that implements the Deutsch-Jozsa algorithm.

Given a Boolean function \(f : \{0, \, 1\}^{n} \to \{0, \, 1\}\) that is promised to be either constant or balanced, i.e. equal to \(1\) for exactly half of the inputs, the algorithm decides which one it is with a single query to the oracle \(U_{f} \ket{x} \ket{y} = \ket{x} \ket{y \oplus f(x)}\), where \(\oplus\) is the sum modulo \(2\). The circuit acts on \(n + 1\) qubits, with the first \(n\) being the input qubits and the last one the output qubit of the oracle, and it is composed of the following steps:

  1. a qibo.gates.X gate on the output qubit, and a Hadamard gate on every qubit;

  2. the oracle \(U_{f}\);

  3. a Hadamard gate on each of the input qubits;

  4. the measurement of the input qubits, if measure=True.

The output qubit is in the state \(\ket{-}\), so that the oracle only multiplies \(\ket{x}\) by \((-1)^{f(x)}\). Then, the probability of measuring the input qubits in the state \(\ket{0}^{\otimes \, n}\) is \(1\) if \(f\) is constant, and \(0\) if it is balanced.

Example

from qibo import Circuit, gates
from qibo.models import DeutschJozsa

# oracle of the balanced function that is equal to the first input bit
oracle = Circuit(4)
oracle.add(gates.CNOT(0, 3))

circuit = DeutschJozsa(oracle)
result = circuit(nshots=10)

# the outcome is not 000, so the function is balanced
print(result.frequencies())

Counter({'100': 10})
Parameters:

  • oracle (qibo.models.circuit.Circuit) – circuit that implements \(U_{f}\), which has \(n + 1\) qubits, with the output qubit being the last one. It cannot contain measurements.

  • measure (bool, optional) – If True, adds a measurement of the input qubits at the end of the circuit. Defaults to True.

  • kwargs (dict, optional) – Additional arguments used to initialize qibo.models.circuit.Circuit, e.g. density_matrix=True. For details, see the documentation of qibo.models.circuit.Circuit.

Returns:

implementation of the Deutsch-Jozsa algorithm.

Return type:

qibo.models.circuit.Circuit

References

1. D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. Lond. A 439, 553 (1992).

2. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited, Proc. R. Soc. Lond. A 454, 339 (1998).

Bernstein-Vazirani#

qibo.models.BernsteinVazirani(oracle, measure=True, **kwargs)[source]#

Creates a circuit that implements the Bernstein-Vazirani algorithm.

Given a Boolean function \(f(x) = s \cdot x \oplus c\), where \(s \in \{0, \, 1\}^{n}\) is a hidden string, \(\cdot\) is the bitwise inner product modulo \(2\), and \(c \in \{0, \, 1\}\), the algorithm finds \(s\) with a single query to the oracle \(U_{f} \ket{x} \ket{y} = \ket{x} \ket{y \oplus f(x)}\), where \(\oplus\) is the sum modulo \(2\). The circuit acts on \(n + 1\) qubits, with the first \(n\) being the input qubits and the last one the output qubit of the oracle. It is the same circuit as the one of qibo.models.DeutschJozsa(): the output qubit is in the state \(\ket{-}\), so that the oracle multiplies \(\ket{x}\) by \((-1)^{s \cdot x}\), which is undone by the Hadamard gates on the input qubits, that are left in the state \(\ket{s}\). If measure=True, the qubit \(k\) of the measured bitstring is the bit \(s_{k}\).

Example

from qibo import Circuit, gates
from qibo.models import BernsteinVazirani

# oracle of the function with the hidden string s = 101
oracle = Circuit(4)
oracle.add(gates.CNOT(0, 3))
oracle.add(gates.CNOT(2, 3))

circuit = BernsteinVazirani(oracle)
result = circuit(nshots=10)

print(result.frequencies())

Counter({'101': 10})
Parameters:

  • oracle (qibo.models.circuit.Circuit) – circuit that implements \(U_{f}\), which has \(n + 1\) qubits, with the output qubit being the last one. It cannot contain measurements.

  • measure (bool, optional) – If True, adds a measurement of the input qubits at the end of the circuit. Defaults to True.

  • kwargs (dict, optional) – Additional arguments used to initialize qibo.models.circuit.Circuit, e.g. density_matrix=True. For details, see the documentation of qibo.models.circuit.Circuit.

Returns:

implementation of the Bernstein-Vazirani algorithm.

Return type:

qibo.models.circuit.Circuit

References

1. E. Bernstein and U. Vazirani, Quantum complexity theory, SIAM J. Comput. 26, 1411 (1997).

2. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited, Proc. R. Soc. Lond. A 454, 339 (1998).

Quantum arithmetic#

Quantum Adders#

qibo.models.Adder(nbits, method='Cuccaro', **kwargs)[source]#

Creates a circuit that adds two integers with the adder chosen by method.

Given two \(n\)-bit non-negative integers \(a\) and \(b\), where \(n\) is nbits, all of the adders perform

\[\ket{a} \, \ket{b} \, \ket{0} \mapsto \ket{a} \, \ket{a + b} \, \ket{0} \, ,\]

where the last register holds the auxiliary qubits, if the adder has any. The first \(n\) qubits hold \(a\), and the next \(n + 1\) qubits hold \(b\), with the overflow bit being the last one, which must be in the state \(\ket{0}\) at the beginning. In every register, the least significant bit comes first. The adders differ in the number of auxiliary qubits and of gates:

Example

from qibo import Circuit, gates
from qibo.models import Adder

nbits = 2
adder = Adder(nbits, method="TTK")

# a = 3 in the qubits 0 and 1, and b = 1 in the qubits 2, 3 and 4
circuit = Circuit(adder.nqubits)
circuit.add(gates.X(0))
circuit.add(gates.X(1))
circuit.add(gates.X(2))
circuit.add(adder)
circuit.add(gates.M(*range(nbits, 2 * nbits + 1)))

result = circuit(nshots=1)
bitstring = next(iter(result.frequencies(binary=True)))

# the least significant bit comes first
print(int(bitstring[::-1], 2))

4
Parameters:

  • nbits (int) – number of bits \(n\) of each of the integers to be added.

  • method (str, optional) – adder to be used. Either "Cuccaro", "DKRS", "Draper", "Gidney", "TTK" or "VBE". Defaults to "Cuccaro".

  • kwargs (dict, optional) – Additional arguments used to initialize qibo.models.circuit.Circuit, e.g. density_matrix=True. For details, see the documentation of qibo.models.circuit.Circuit.

Returns:

implementation of the chosen adder.

Return type:

qibo.models.circuit.Circuit

References

1. S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, A new quantum ripple-carry addition circuit, arXiv:quant-ph/0410184.

2. T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore, A logarithmic-depth quantum carry-lookahead adder, Quantum Inf. Comput. 6, 351 (2006).

3. T. G. Draper, Addition on a Quantum Computer, arXiv:quant-ph/0008033.

4. C. Gidney, Halving the cost of quantum addition, Quantum 2, 74 (2018).

5. Y. Takahashi, S. Tani, and N. Kunihiro, Quantum addition circuits and unbounded fan-out, Quantum Inf. Comput. 10, 872 (2010).

6. V. Vedral, A. Barenco, and A. Ekert, Quantum networks for elementary arithmetic operations, Phys. Rev. A 54, 147 (1996).

qibo.models.Cuccaro(nbits, **kwargs)[source]#

Creates a circuit that implements the Cuccaro-Draper-Kutin-Moulton ripple-carry adder.

Given two \(n\)-bit non-negative integers \(a\) and \(b\), where \(n\) is nbits, the circuit performs

\[\ket{a} \, \ket{b} \, \ket{0} \mapsto \ket{a} \, \ket{a + b \bmod 2^{n + 1}} \, \ket{0} \, .\]

It acts on \(2n + 2\) qubits, which are split into three registers:

  1. the first \(n\) qubits hold \(a\), which is left unchanged;

  2. the next \(n + 1\) qubits hold \(b\), which is replaced by \(a + b\). The last qubit of this register is the overflow bit, which is in the state \(\ket{0}\) at the beginning if \(b < 2^{n}\), so that the sum is exact;

  3. the last qubit is a single auxiliary qubit, the carry-in. It must be in the state \(\ket{0}\) at the beginning, and it is returned to it at the end.

In every register, the \(k\)-th qubit holds the bit \(2^{k}\), i.e. the least significant bit comes first. The circuit is composed of \(n\) majority (MAJ) blocks, which compute the carries in place, a qibo.gates.CNOT that copies the last carry into the overflow qubit, and \(n\) unmajority-and-add (UMA) blocks, which uncompute the carries and write the sum bits, in reverse order. The MAJ and UMA blocks are the ones of Ref. [1], with the version of UMA that has two qibo.gates.CNOT gates, and the circuit is the simple adder of that reference, in which the blocks are applied in sequence. It has \(2n\) qibo.gates.TOFFOLI gates and \(4n + 1\) qibo.gates.CNOT gates. The depth-optimized circuit of Ref. [1], with \(2n - 1\) qibo.gates.TOFFOLI gates, \(5n - 3\) qibo.gates.CNOT gates, and depth \(2n + 4\), is not implemented.

Example

from qibo import Circuit, gates
from qibo.models import Cuccaro

nbits = 2
adder = Cuccaro(nbits)

# a = 3 in the qubits 0 and 1, and b = 1 in the qubits 2, 3 and 4
circuit = Circuit(adder.nqubits)
circuit.add(gates.X(0))
circuit.add(gates.X(1))
circuit.add(gates.X(2))
circuit.add(adder)
circuit.add(gates.M(*range(nbits, 2 * nbits + 1)))

result = circuit(nshots=1)
bitstring = next(iter(result.frequencies(binary=True)))

# the least significant bit comes first
print(int(bitstring[::-1], 2))

4
Parameters:
Returns:

implementation of the Cuccaro ripple-carry adder.

Return type:

qibo.models.circuit.Circuit

References

1. S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, A new quantum ripple-carry addition circuit, arXiv:quant-ph/0410184.

qibo.models.DKRS(nbits, **kwargs)[source]#

Creates a circuit that implements the Draper-Kutin-Rains-Svore (DKRS) carry-lookahead adder.

Given two \(n\)-bit non-negative integers \(a\) and \(b\), where \(n\) is nbits, the circuit performs

\[\ket{a} \, \ket{b} \, \ket{0} \mapsto \ket{a} \, \ket{a + b} \, \ket{0} \, .\]

It acts on \(3n + 2 + m\) qubits, with \(m = n - w(n) - \lfloor \log_{2} n \rfloor\) and \(w(n)\) being the number of ones in the binary representation of \(n\). The qubits are split into three registers:

  1. the first \(n\) qubits hold \(a\), which is left unchanged;

  2. the next \(n + 1\) qubits hold \(b\), which is replaced by \(a + b\). The last qubit of this register is the overflow bit, which must be in the state \(\ket{0}\) at the beginning;

  3. the last \(n + 1 + m\) qubits are auxiliary qubits. They must be in the state \(\ket{0}\) at the beginning, and they are returned to it at the end.

In every register, the \(k\)-th qubit holds the bit \(2^{k}\), i.e. the least significant bit comes first. The carries are computed with a tree of qibo.gates.TOFFOLI gates, so that the depth of the circuit is logarithmic in \(n\). The sum is first written in the auxiliary qubits by an out-of-place adder. Then, the inverse of the same adder, applied to the complement of the sum, erases \(b\), and the registers are swapped. Each out-of-place adder is the one of Section 4.1 of Ref. [1], with \(5n - 3 w(n) - 3 \lfloor \log_{2} n \rfloor - 1\) qibo.gates.TOFFOLI gates, so the circuit has twice as many, and, for \(n \geq 4\), its Toffoli depth is \(2 (\lfloor \log_{2} n \rfloor + \lfloor \log_{2} (n / 3) \rfloor + 4)\). This is not the in-place construction of Section 4.2 of Ref. [1], which erases only the carries: it needs two more auxiliary qubits than the \(2n - w(n) - \lfloor \log_{2} n \rfloor - 1\) of that construction.

Example

from qibo import Circuit, gates
from qibo.models import DKRS

nbits = 2
adder = DKRS(nbits)

# a = 3 in the qubits 0 and 1, and b = 1 in the qubits 2, 3 and 4
circuit = Circuit(adder.nqubits)
circuit.add(gates.X(0))
circuit.add(gates.X(1))
circuit.add(gates.X(2))
circuit.add(adder)
circuit.add(gates.M(*range(nbits, 2 * nbits + 1)))

result = circuit(nshots=1)
bitstring = next(iter(result.frequencies(binary=True)))

# the least significant bit comes first
print(int(bitstring[::-1], 2))

4
Parameters:
Returns:

implementation of the DKRS adder.

Return type:

qibo.models.circuit.Circuit

References

1. T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore, A logarithmic-depth quantum carry-lookahead adder, Quantum Inf. Comput. 6, 351 (2006).

qibo.models.Draper(nbits, **kwargs)[source]#

Creates a circuit that implements the Draper quantum Fourier transform (QFT) adder.

Given two \(n\)-bit non-negative integers \(a\) and \(b\), where \(n\) is nbits, the circuit performs

\[\ket{a} \, \ket{b} \mapsto \ket{a} \, \ket{a + b \bmod 2^{n + 1}} \, .\]

It acts on \(2n + 1\) qubits, and it does not need auxiliary qubits. The first \(n\) qubits hold \(a\), which is left unchanged, and the last \(n + 1\) qubits hold \(b\), which is replaced by \(a + b\). The last qubit of the second register is the overflow bit, which is in the state \(\ket{0}\) at the beginning if \(b < 2^{n}\), so that the sum is exact.

In every register, the \(k\)-th qubit holds the bit \(2^{k}\), i.e. the least significant bit comes first. The circuit is composed of the following steps:

  1. the qibo.models.QFT on the register of \(b\), without swaps;

  2. qibo.gates.CU1 gates, controlled by the qubits of \(a\), which add \(a\) to \(b\) in the Fourier basis, by rotating the phases of the qubits of \(b\);

  3. the inverse qibo.models.QFT on the register of \(b\), without swaps.

The smallest rotation angle is \(2 \pi / 2^{n + 1}\).

Example

from qibo import Circuit, gates
from qibo.models import Draper

nbits = 2
adder = Draper(nbits)

# a = 3 in the qubits 0 and 1, and b = 1 in the qubits 2, 3 and 4
circuit = Circuit(adder.nqubits)
circuit.add(gates.X(0))
circuit.add(gates.X(1))
circuit.add(gates.X(2))
circuit.add(adder)
circuit.add(gates.M(*range(nbits, 2 * nbits + 1)))

result = circuit(nshots=1)
bitstring = next(iter(result.frequencies(binary=True)))

# the least significant bit comes first
print(int(bitstring[::-1], 2))

4
Parameters:
Returns:

implementation of the Draper adder.

Return type:

qibo.models.circuit.Circuit

References

1. T. G. Draper, Addition on a Quantum Computer, arXiv:quant-ph/0008033.

qibo.models.Gidney(nbits, **kwargs)[source]#

Creates a circuit that implements the Gidney adder.

Given two \(n\)-bit non-negative integers \(a\) and \(b\), where \(n\) is nbits, the circuit performs

\[\ket{a} \, \ket{b} \, \ket{0} \mapsto \ket{a} \, \ket{a + b} \, \ket{0} \, .\]

It acts on \(3n\) qubits, which are split into three registers:

  1. the first \(n\) qubits hold \(a\), which is left unchanged;

  2. the next \(n + 1\) qubits hold \(b\), which is replaced by \(a + b\). The last qubit of this register is the overflow bit, which must be in the state \(\ket{0}\) at the beginning;

  3. the last \(n - 1\) qubits are auxiliary qubits that store the carries. They must be in the state \(\ket{0}\) at the beginning, and they are returned to it at the end.

In every register, the \(k\)-th qubit holds the bit \(2^{k}\), i.e. the least significant bit comes first. Each carry is computed in a qubit in the state \(\ket{0}\) with a temporary logical-AND, which has four qibo.gates.T or qibo.gates.TDG gates. Then, it is erased without them: the qubit is measured in the \(X\) basis, and, if the outcome is \(1\), a qibo.gates.CZ gate, which is applied with a qibo.gates.CU1 conditioned on the outcome, fixes the phase. Hence, the circuit has \(4n\) of these gates, and \(n - 1\) measurements with collapse set to True. Because of them, each shot has to be simulated separately, and the circuit cannot be inverted. Ref. [1] presents the adder without the carry out, which has \(n - 1\) temporary logical-ANDs and \(4n - 4\) of these gates. Here, the carry out takes one more temporary logical-AND.

Example

from qibo import Circuit, gates
from qibo.models import Gidney

nbits = 2
adder = Gidney(nbits)

# a = 3 in the qubits 0 and 1, and b = 1 in the qubits 2, 3 and 4
circuit = Circuit(adder.nqubits)
circuit.add(gates.X(0))
circuit.add(gates.X(1))
circuit.add(gates.X(2))
circuit.add(adder)
circuit.add(gates.M(*range(nbits, 2 * nbits + 1)))

result = circuit(nshots=1)
bitstring = next(iter(result.frequencies(binary=True)))

# the least significant bit comes first
print(int(bitstring[::-1], 2))

4
Parameters:
Returns:

implementation of the Gidney adder.

Return type:

qibo.models.circuit.Circuit

References

1. C. Gidney, Halving the cost of quantum addition, Quantum 2, 74 (2018).

qibo.models.TTK(nbits, **kwargs)[source]#

Creates a circuit that implements the Takahashi-Tani-Kunihiro (TTK) adder.

Given two \(n\)-bit non-negative integers \(a\) and \(b\), where \(n\) is nbits, the circuit performs

\[\ket{a} \, \ket{b} \mapsto \ket{a} \, \ket{a + b \bmod 2^{n + 1}} \, .\]

It acts on \(2n + 1\) qubits, and it does not need auxiliary qubits. The first \(n\) qubits hold \(a\), which is left unchanged, and the last \(n + 1\) qubits hold \(b\), which is replaced by \(a + b\). The last qubit of the second register is the overflow bit, which is in the state \(\ket{0}\) at the beginning if \(b < 2^{n}\), so that the sum is exact.

In every register, the \(k\)-th qubit holds the bit \(2^{k}\), i.e. the least significant bit comes first. The circuit only has qibo.gates.TOFFOLI and qibo.gates.CNOT gates. The carries are computed in place, using the qubits of \(a\), and then uncomputed while the sum bits are written in \(b\). For \(n \geq 2\), it has \(2n - 1\) qibo.gates.TOFFOLI gates and \(5n - 5\) qibo.gates.CNOT gates, which is the size \(7n - 6\) of Ref. [1]. For \(n = 1\), it is a half adder, with one of each.

Example

from qibo import Circuit, gates
from qibo.models import TTK

nbits = 2
adder = TTK(nbits)

# a = 3 in the qubits 0 and 1, and b = 1 in the qubits 2, 3 and 4
circuit = Circuit(adder.nqubits)
circuit.add(gates.X(0))
circuit.add(gates.X(1))
circuit.add(gates.X(2))
circuit.add(adder)
circuit.add(gates.M(*range(nbits, 2 * nbits + 1)))

result = circuit(nshots=1)
bitstring = next(iter(result.frequencies(binary=True)))

# the least significant bit comes first
print(int(bitstring[::-1], 2))

4
Parameters:
Returns:

implementation of the TTK adder.

Return type:

qibo.models.circuit.Circuit

References

1. Y. Takahashi, S. Tani, and N. Kunihiro, Quantum addition circuits and unbounded fan-out, Quantum Inf. Comput. 10, 872 (2010).

qibo.models.VBE(nbits, **kwargs)[source]#

Creates a circuit that implements the Vedral-Barenco-Ekert (VBE) plain adder.

Given two \(n\)-bit non-negative integers \(a\) and \(b\), where \(n\) is nbits, the circuit performs

\[\ket{a} \, \ket{b} \, \ket{0} \mapsto \ket{a} \, \ket{a + b} \, \ket{0} \, .\]

It acts on \(3n + 1\) qubits, which are split into three registers:

  1. the first \(n\) qubits hold \(a\), which is left unchanged;

  2. the next \(n + 1\) qubits hold \(b\), which is replaced by \(a + b\). The last qubit of this register is the overflow bit, and it must be in the state \(\ket{0}\) at the beginning;

  3. the last \(n\) qubits are auxiliary qubits that store the carries. They must be in the state \(\ket{0}\) at the beginning, and they are returned to it at the end.

In every register, the \(k\)-th qubit holds the bit \(2^{k}\), i.e. the least significant bit comes first. The circuit is composed of \(n\) blocks that compute the carries, followed by blocks that compute the sum bits while the carries are uncomputed, in reverse order. It has \(4n - 2\) qibo.gates.TOFFOLI gates and \(4n\) qibo.gates.CNOT gates. The carries \(c_{0}, \dots, c_{n - 1}\) are stored in the auxiliary qubits, with \(c_{0} = 0\), and the carry \(c_{n}\) in the overflow qubit.

Example

from qibo import Circuit, gates
from qibo.models import VBE

nbits = 2
adder = VBE(nbits)

# a = 3 in the qubits 0 and 1, and b = 1 in the qubits 2, 3 and 4
circuit = Circuit(adder.nqubits)
circuit.add(gates.X(0))
circuit.add(gates.X(1))
circuit.add(gates.X(2))
circuit.add(adder)
circuit.add(gates.M(*range(nbits, 2 * nbits + 1)))

result = circuit(nshots=1)
bitstring = next(iter(result.frequencies(binary=True)))

# the least significant bit comes first
print(int(bitstring[::-1], 2))

4
Parameters:
Returns:

implementation of the VBE plain adder.

Return type:

qibo.models.circuit.Circuit

References

1. V. Vedral, A. Barenco, and A. Ekert, Quantum networks for elementary arithmetic operations, Phys. Rev. A 54, 147 (1996).

Block encodings and signal processing#

Block Encoding#

qibo.models.block_encoding_circuit(matrix, method='dense', alpha=None, backend=None)[source]#

Creates a block encoding of a matrix.

Let \(A\) be matrix, a square matrix that is padded with zeros up to dimension \(2^{n}\) if needed, with \(n \ge 1\). The circuit acts on \(a\) auxiliary qubits, followed by \(n\) system qubits, and the block of its unitary in which the auxiliary qubits start and end in \(\ket{0}\) is \(A / \alpha\), where \(\alpha\) is a normalization. This is a block encoding as in Definition 24 of Ref. [1], with zero error, and the zero padding is the embedding of that reference. Both methods have a cost that grows exponentially with \(n\).

  • method="dense": \(a = 1\). With \(B = A / \alpha\), whose singular values are at most one, the circuit is a single gate for the unitary dilation

    \[\begin{split}U = \begin{pmatrix} B & \sqrt{\mathbb{1} - B B^{\dagger}} \\ \sqrt{\mathbb{1} - B^{\dagger} B} & -B^{\dagger} \end{pmatrix},\end{split}\]

    where \(\mathbb{1}\) is the identity and \(B^{\dagger}\) the conjugate transpose of \(B\). The matrix square roots are computed from the singular value decomposition of \(B\). In the basis of the singular vectors, \(U\) is made of the \(2 \times 2\) blocks of Eq. (4) of Ref. [1].

  • method="lcu": the matrix is decomposed as a sum of Pauli strings, \(A = \sum_{i} c_{i} P_{i}\), with complex coefficients \(c_{i}\), and the circuit is the one of qibo.models.lcu_circuit(). The normalization is \(\alpha = \sum_{i} |c_{i}|\), and \(a = \max(1, \lceil \log_{2} L \rceil)\), with \(L\) the number of non-zero coefficients. Pauli strings are trivial block encodings of themselves, so this is Lemma 29 of Ref. [1].

Example

Encode \(X / 2\), with \(X\) the Pauli-\(X\) matrix. The amplitudes with the auxiliary qubits in \(\ket{0}\) are those of \(\ket{1} / 2\) for the dense method, and those of \(\ket{1}\) for the LCU method, whose normalization is \(1 / 2\).

from qibo import get_backend
from qibo.models import block_encoding_circuit

backend = get_backend()

matrix = 0.5 * backend.matrices.X

circuit, alpha, nauxiliary = block_encoding_circuit(matrix)
state = circuit().state()[:2]
print(backend.allclose(state, backend.cast([0.0, 0.5])), alpha, nauxiliary)

circuit, alpha, nauxiliary = block_encoding_circuit(matrix, method="lcu")
state = circuit().state()[:2]
print(backend.allclose(state, backend.cast([0.0, 1.0])), alpha, nauxiliary)

True 1.0 1
True 0.5 1
Parameters:

  • matrix (ArrayLike) – square matrix \(A\).

  • method (str, optional) – "dense" for the unitary dilation or "lcu" for the linear combination of unitaries of the Pauli strings. Defaults to "dense".

  • alpha (float, optional) – normalization \(\alpha\) if method="dense", which has to be at least the spectral norm of matrix. If None, it is the spectral norm if this is larger than one, and one otherwise. It is not used by method="lcu", for which it has to be None. Defaults to None.

  • backend (qibo.backends.abstract.Backend, optional) – backend to be used in the calculation. If None, it uses the current backend. Defaults to None.

Returns:

circuit on \(a + n\) qubits, with the auxiliary qubits at the first qubits, the normalization \(\alpha\), and the number \(a\) of auxiliary qubits. The circuit and the number of auxiliary qubits are the arguments of qibo.models.qsvt_circuit().

Return type:

tuple

References

1. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC ‘19), 193-204 (2019).

Linear Combination of Unitaries#

qibo.models.lcu_circuit(unitaries, coefficients, backend=None)[source]#

Creates a linear combination of unitaries (LCU) circuit.

Let \(U_{i}\) be the unitary of the \(i\)-th circuit of unitaries, with \(i = 0, \dots, L - 1\), let \(c_{i}\) be its complex coefficient, and let \(\alpha = \sum_{i} |c_{i}|\). The circuit acts on \(a = \max(1, \lceil \log_{2} L \rceil)\) auxiliary qubits, followed by the qubits of the unitaries, and block-encodes the operator \(A / \alpha\), with \(A = \sum_{i} c_{i} U_{i}\). That is, the block of the circuit unitary in which the auxiliary qubits start and end in \(\ket{0}\) is \(A / \alpha\). The circuit is \(\mathrm{PREPARE}_{L}^{\dagger} \, \mathrm{SELECT} \, \mathrm{PREPARE}_{R}\), where \(\mathrm{PREPARE}_{L}\) and \(\mathrm{PREPARE}_{R}\) are created with qibo.models.lcu_prepare(), and \(\mathrm{SELECT}\) is created with qibo.models.lcu_select().

This is the block encoding of Lemma 29 of Ref. [2], with \((\mathrm{PREPARE}_{L}, \mathrm{PREPARE}_{R})\) a state-preparation pair (Definition 28 of Ref. [2]). For \(L = 2\) and the coefficients \((\kappa, 1)\), it is the circuit of Lemma 2 of Ref. [1], which fails, i.e. the auxiliary qubit is not in \(\ket{0}\), with probability \(\kappa \| (U_{1} - U_{0}) \ket{\psi} \|^{2} / (\kappa + 1)^{2}\) for the input state \(\ket{\psi}\).

Example

Apply \((X + Z) / 2\) to \(\ket{0}\), where \(X\) and \(Z\) are Pauli matrices. The amplitudes with the auxiliary qubit in \(\ket{0}\) are those of \(\ket{+} / \sqrt{2}\).

from qibo import Circuit, gates, get_backend
from qibo.models import lcu_circuit

backend = get_backend()

pauli_x = Circuit(1)
pauli_x.add(gates.X(0))
pauli_z = Circuit(1)
pauli_z.add(gates.Z(0))
circuit, alpha, nauxiliary = lcu_circuit([pauli_x, pauli_z], [0.5, 0.5])

target = Circuit(1)
target.add(gates.H(0))

state = circuit().state()[:2]
print(
    backend.allclose(state, target().state() / backend.sqrt(2)),
    alpha,
    nauxiliary,
)

True 1.0 1
Parameters:

  • unitaries (list[qibo.models.circuit.Circuit]) – circuits on the same number of qubits that implement \(U_{i}\). They have to be exact, including their global phase, since they are applied under control.

  • coefficients (ArrayLike) – one-dimensional array of the (complex) coefficients \(c_{i}\), with at least one non-zero element.

  • backend (qibo.backends.abstract.Backend, optional) – backend to be used in the calculation. If None, it uses the current backend. Defaults to None.

Returns:

the circuit, with the auxiliary qubits at the first qubits, the normalization \(\alpha\), and the number \(a\) of auxiliary qubits. The last two are the arguments of qibo.models.qsvt_circuit() for which the circuit is a block encoding of \(A / \alpha\).

Return type:

tuple

References

1. A. M. Childs and N. Wiebe, Hamiltonian simulation using linear combinations of unitary operations, Quantum Information & Computation 12, 901-924 (2012). 2. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC ‘19), 193-204 (2019).

qibo.models.lcu_prepare(coefficients, backend=None)[source]#

Creates the \(\mathrm{PREPARE}\) oracles of a linear combination of unitaries (LCU).

Let \(c_{i}\) be the \(i\)-th (complex) element of coefficients, with \(i = 0, \dots, L - 1\), and let \(\alpha = \sum_{i} |c_{i}|\). The oracles act on \(a = \max(1, \lceil \log_{2} L \rceil)\) auxiliary qubits. When applied to \(\ket{0}\), \(\mathrm{PREPARE}_{L}\) and \(\mathrm{PREPARE}_{R}\) load the amplitudes

\[\mathrm{PREPARE}_{L} \ket{0} = \sum_{i} \sqrt{\frac{|c_{i}|}{\alpha}} \, \ket{i} \quad \text{and} \quad \mathrm{PREPARE}_{R} \ket{0} = \sum_{i} \sqrt{\frac{|c_{i}|}{\alpha}} \, \frac{c_{i}}{|c_{i}|} \, \ket{i} \, ,\]

respectively, with the amplitudes of \(\ket{i}\), for \(i \geq L\), set to zero. For real and non-negative coefficients, they are the same oracle. The oracles are built with qibo.models.encodings.binary_encoder(), with the Mottonen parametrization, since the resulting circuits have an exact inverse. Together with qibo.models.lcu_select(), they build the block encoding \(\mathrm{PREPARE}_{L}^{\dagger} \, \mathrm{SELECT} \, \mathrm{PREPARE}_{R}\) of \(\sum_{i} c_{i} U_{i} / \alpha\). They are a state-preparation pair in the sense of Definition 28 of Ref. [2].

Example

Prepare the amplitudes of the coefficients \(3\) and \(-1\), for which \(\alpha = 4\).

from qibo import get_backend
from qibo.models import lcu_prepare

backend = get_backend()

prepare_left, prepare_right, alpha, nauxiliary = lcu_prepare([3.0, -1.0])

left = backend.cast([0.75**0.5, 0.25**0.5], dtype="complex128")
right = backend.cast([0.75**0.5, -(0.25**0.5)], dtype="complex128")

print(
    backend.allclose(prepare_left().state(), left),
    backend.allclose(prepare_right().state(), right),
    alpha,
    nauxiliary,
)

True True 4.0 1
Parameters:

  • coefficients (ArrayLike) – one-dimensional array of the (complex) coefficients \(c_{i}\), with at least one non-zero element.

  • backend (qibo.backends.abstract.Backend, optional) – backend to be used in the calculation. If None, it uses the current backend. Defaults to None.

Returns:

the circuits of \(\mathrm{PREPARE}_{L}\) and \(\mathrm{PREPARE}_{R}\), both on \(a\) qubits, the normalization \(\alpha\), and the number \(a\) of auxiliary qubits.

Return type:

tuple

References

1. A. M. Childs and N. Wiebe, Hamiltonian simulation using linear combinations of unitary operations, Quantum Information & Computation 12, 901-924 (2012). 2. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC ‘19), 193-204 (2019).

qibo.models.lcu_select(unitaries, nauxiliary=None, backend=None)[source]#

Creates the \(\mathrm{SELECT}\) oracle of a linear combination of unitaries (LCU).

Let \(U_{i}\) be the unitary of the \(i\)-th circuit of unitaries, with \(i = 0, \dots, L - 1\). The oracle acts on \(a\) auxiliary qubits, followed by the qubits of the unitaries, and applies \(U_{i}\) to the latter when the auxiliary qubits are in the computational basis state \(\ket{i}\),

\[\mathrm{SELECT} = \sum_{i = 0}^{L - 1} \ket{i}\!\bra{i} \otimes U_{i} + \sum_{i = L}^{2^{a} - 1} \ket{i}\!\bra{i} \otimes I \, .\]

Each unitary is applied under the control of all the auxiliary qubits, with \(X\) gates that map \(\ket{i}\) into \(\ket{1 \dots 1}\). Gates that are already controlled are supported. A unitary with no gates is the identity, and is skipped. It is the unitary \(W\) of Lemma 29 of Ref. [2].

Example

Apply the Pauli matrices \(X\) and \(Z\) to \(\ket{0}\), selected by an auxiliary qubit in \(\ket{+}\). The state is \((\ket{0}\ket{1} + \ket{1}\ket{0}) / \sqrt{2}\).

from qibo import Circuit, gates, get_backend
from qibo.models import lcu_select

backend = get_backend()

pauli_x = Circuit(1)
pauli_x.add(gates.X(0))
pauli_z = Circuit(1)
pauli_z.add(gates.Z(0))
select = lcu_select([pauli_x, pauli_z])

circuit = Circuit(2)
circuit.add(gates.H(0))
circuit.add(select.on_qubits(0, 1))

target = backend.cast([0.0, 1.0, 1.0, 0.0], dtype="complex128")

print(backend.allclose(circuit().state(), target / backend.sqrt(2)))

True
Parameters:

  • unitaries (list[qibo.models.circuit.Circuit]) – circuits on the same number of qubits that implement \(U_{i}\). They have to be exact, including their global phase, since they are applied under control.

  • nauxiliary (int, optional) – number \(a\) of auxiliary qubits. It has to satisfy \(2^{a} \geq L\). If None, it is \(\max(1, \lceil \log_{2} L \rceil)\). Defaults to None.

  • backend (qibo.backends.abstract.Backend, optional) – backend to be used in the calculation. If None, it uses the current backend. Defaults to None.

Returns:

circuit of \(\mathrm{SELECT}\), with the auxiliary qubits at the first qubits.

Return type:

qibo.models.circuit.Circuit

References

1. A. M. Childs and N. Wiebe, Hamiltonian simulation using linear combinations of unitary operations, Quantum Information & Computation 12, 901-924 (2012). 2. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC ‘19), 193-204 (2019).

Quantum Signal Processing#

qibo.models.qsp_phases(coefficients, sine_coefficients=None, method=None, extraction='phase_sums', backend=None)[source]#

Computes the phases of a quantum signal processing (QSP) circuit.

  • method=None: QSP of Ref. [1]. Given the series \(A(\theta) = \sum_{k = 0}^{N/2} a_{k} \cos(k \theta)\) and \(C(\theta) = \sum_{k = 1}^{N/2} c_{k} \sin(k \theta)\), with even \(N\), it finds \(N\) phases such that \(\langle + | V(\theta) | + \rangle = A(\theta) + i C(\theta)\). Here, \(V(\theta)\) is the product of the \(N\) single-qubit rotations of angle \(\theta\) about the axes of the \(xy\)-plane given by the phases, and \(|+\rangle\) is the \(+1\) eigenstate of the Pauli- \(X\) operator. Since \(V(0)\) is the identity, the target has to satisfy \(A(0) = 1\). It is rescaled if \(|A + i C| > 1\).

  • method="fourier": Fourier-based QSP of Ref. [2]. Given the coefficients \(c_{m}\) of the Fourier series \(\tilde{g}(x) = \sum_{m = -q/2}^{q/2} c_{m} \, e^{i m x}\), with even \(q\), it finds the angles of \(q + 1\) single-qubit gates whose product has \(\tilde{g}(x)\) as its upper-left matrix element. The series is divided by \(\max_{x} |\tilde{g}(x)|\) if it is larger than one.

The complementary series is computed numerically, which requires the target to be strictly bounded by one. Hence, the accuracy of the circuit is limited. If method="fourier", the block of the circuit matches \(\tilde{g}\) to machine precision if \(\max_{x} |\tilde{g}(x)| \leq 0.99\), but the error can reach \(10^{-2}\) for values closer to one, which includes the series that are divided by \(\max_{x} |\tilde{g}(x)|\). If method=None, the error can be of the order of \(10^{-6}\), because \(|A + i C| = 1\) at \(\theta = 0\).

Parameters:

  • coefficients (ArrayLike) – if method=None, cosine coefficients \((a_{0}, \dots, a_{N/2})\). If method="fourier", Fourier coefficients \((c_{-q/2}, \dots, c_{q/2})\).

  • sine_coefficients (ArrayLike, optional) – sine coefficients \((c_{1}, \dots, c_{N/2})\). Required if method=None and not used otherwise. Defaults to None.

  • method (str, optional) – None for QSP of Ref. [1] or "fourier" for Fourier-based QSP of Ref. [2]. Defaults to None.

  • extraction (str, optional) – how the phases are extracted if method=None. "phase_sums" follows Ref. [3] and loses precision for \(N \gtrsim 30\), while "layer_stripping" removes one rotation at a time and stays accurate for larger \(N\). Defaults to "phase_sums".

  • backend (qibo.backends.abstract.Backend, optional) – backend to be used in the calculation. If None, it uses the current backend. Defaults to None.

Returns:

phases for qibo.models.qsp_circuit() with the same method. An array of length \(N\) if method=None, or an array of shape \((q + 1, 4)\) if method="fourier".

Return type:

ArrayLike

References

1. G. H. Low and I. L. Chuang, Optimal Hamiltonian Simulation by Quantum Signal Processing, Phys. Rev. Lett. 118, 010501 (2017). 2. T. L. Silva, L. Borges, and L. Aolita, Fourier-based quantum signal processing, arXiv:2206.02826. 3. G. H. Low, T. J. Yoder, and I. L. Chuang, The methodology of resonant equiangular composite quantum gates, Phys. Rev. X 6, 041067 (2016).

qibo.models.qsp_circuit(oracle, phases, method=None)[source]#

Creates a quantum signal processing (QSP) circuit.

The circuit interleaves queries to oracle with rotations of an auxiliary qubit, placed at qubit \(0\). The remaining qubits are those of oracle.

  • method=None: QSP of Ref. [1]. oracle implements a unitary \(W\), which is queried \(N\) times. The block of the circuit unitary with the auxiliary qubit starting and ending in \(|0\rangle\) applies \(A(\theta) + i C(\theta)\) to each eigenphase \(\theta\) of \(W\), where \(A\) and \(C\) are the trigonometric polynomials encoded in phases.

  • method="fourier": Fourier-based QSP of Ref. [2]. oracle implements \(e^{-i t H}\) for a Hermitian operator \(H\) and a time \(t\), and is queried \(q\) times under control. The same block of the circuit unitary is \(\tilde{g}(H t)\), where \(\tilde{g}\) is the Fourier series encoded in phases.

Example

Apply \((1 + W) / 2\), with \(W = X\), to \(|0\rangle\). The amplitudes with the auxiliary qubit in \(|0\rangle\) are those of \(|+\rangle / \sqrt{2}\).

from qibo import Circuit, gates, get_backend
from qibo.models import qsp_circuit, qsp_phases

backend = get_backend()

walk = Circuit(1)
walk.add(gates.X(0))

# cosine and sine series of (1 + exp(i theta)) / 2
phases = qsp_phases([0.5, 0.5], [0.5])
circuit = qsp_circuit(walk, phases)

target = Circuit(1)
target.add(gates.H(0))

state = circuit().state()[:2]
print(backend.allclose(state, target().state() / backend.sqrt(2), atol=1e-4))

True

Invert a rotation with the Fourier series \(\tilde{g}(x) = e^{i x}\). The amplitudes with the auxiliary qubit in \(|0\rangle\) are those of the inverse rotation applied to \(|0\rangle\).

from qibo import Circuit, gates, get_backend
from qibo.models import qsp_circuit, qsp_phases

backend = get_backend()

evolution = Circuit(1)
evolution.add(gates.RX(0, 0.6))

# coefficients of exp(-i x), 1, and exp(i x)
phases = qsp_phases([0.0, 0.0, 1.0], method="fourier")
circuit = qsp_circuit(evolution, phases, method="fourier")

target = Circuit(1)
target.add(gates.RX(0, -0.6))

state = circuit().state()[:2]
print(backend.allclose(state, target().state(), atol=1e-6))

True
Parameters:

  • oracle (qibo.models.circuit.Circuit) – circuit on \(n\) qubits that implements \(W\) or \(e^{-i t H}\), depending on method. It has to be exact, including its global phase, since it is applied under control.

  • phases (ArrayLike) – output of qibo.models.qsp_phases() for the same method.

  • method (str, optional) – None for QSP of Ref. [1] or "fourier" for Fourier-based QSP of Ref. [2]. Defaults to None.

Returns:

circuit on \(n + 1\) qubits, with the auxiliary qubit at qubit \(0\).

Return type:

qibo.models.circuit.Circuit

References

1. G. H. Low and I. L. Chuang, Optimal Hamiltonian Simulation by Quantum Signal Processing, Phys. Rev. Lett. 118, 010501 (2017). 2. T. L. Silva, L. Borges, and L. Aolita, Fourier-based quantum signal processing, arXiv:2206.02826.

Quantum Singular Value Transformation#

qibo.models.qsvt_phases(coefficients, backend=None)[source]#

Computes the phases of a quantum singular value transformation (QSVT) circuit.

Given the Chebyshev series \(P(x) = \sum_{k = 0}^{d} c_{k} T_{k}(x)\) of a real polynomial of degree \(d \ge 1\) with the parity of \(d\) and \(|P(x)| \le 1\) for \(x \in [-1, 1]\), it finds the phases for which qibo.models.qsvt_circuit() applies \(P\) to the singular values (Corollary 11 of Ref. [1]). The polynomial is completed into a unitary matrix whose entries are trigonometric polynomials, using the spectral factorization of \(1 - P^{2}\) that qibo.models.qsp_phases() uses for the Fourier-based QSP, and the phases are then extracted one at a time as in Ref. [2].

The coefficients are divided by its (grid-estimated) \(\max_{x} |P(x)|\) if it is larger than one. If \(|P|\) reaches one, the polynomial is implemented with a relative error of about \(10^{-6}\) for degrees up to \(100\) and \(10^{-5}\) up to \(300\), and the error is much smaller for polynomials that stay away from one.

Parameters:

  • coefficients (ArrayLike) – Chebyshev coefficients \((c_{0}, \dots, c_{d})\). The degree is that of the last non-zero coefficient, and the coefficients of the opposite parity must vanish. Those with modulus below \(10^{-12}\) times the largest one are taken as zero.

  • backend (qibo.backends.abstract.Backend, optional) – backend to be used in the calculation. If None, it uses the current backend. Defaults to None.

Returns:

\(d + 1\) phases. The first \(d\) are those of the rotations controlled by the projector, in the order that they are applied, and the last one is the final rotation of the signal qubit.

Return type:

ArrayLike

References

1. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC ‘19), 193-204 (2019). 2. J. Haah, Product decomposition of periodic functions in quantum signal processing, Quantum 3, 190 (2019).

qibo.models.qsvt_circuit(block_encoding, phases, nancillas)[source]#

Creates a quantum singular value transformation (QSVT) circuit.

Let \(U\) be the unitary of block_encoding, which acts on \(a\) auxiliary qubits and \(n\) system qubits, and let \(A = (\bra{0}^{\otimes a} \otimes \mathbb{1}) \, U \, (\ket{0}^{\otimes a} \otimes \mathbb{1})\) be the matrix that it encodes, with singular value decomposition \(A = \sum_{i} \varsigma_{i} \ket{w_{i}}\!\bra{v_{i}}\). The block of the circuit unitary in which the signal qubit and the auxiliary qubits start and end in \(\ket{0}\) applies a polynomial \(P\) of degree \(d\) to the singular values,

\[\begin{split}P^{(SV)}(A) = \begin{cases} \sum_{i} P(\varsigma_{i}) \, \ket{w_{i}}\!\bra{v_{i}} & d \text{ odd,} \\ \sum_{i} P(\varsigma_{i}) \, \ket{v_{i}}\!\bra{v_{i}} & d \text{ even.} \end{cases}\end{split}\]

The circuit queries \(U\) and \(U^{\dagger}\) alternately \(d\) times (Theorem 2 of Ref. [1]) and uses a single extra qubit, the signal qubit, which controls the sign of the phases of the rotations that are controlled by the projector on the auxiliary qubits in \(|0\rangle\).

Example

Apply the cubic Chebyshev polynomial \(T_{3}(x) = 4 x^{3} - 3 x\) to the singular value \(1/2\) of a block-encoding of \(\ket{+} / 2\). Since \(T_{3}(1/2) = -1\), the amplitudes with the signal qubit and the auxiliary qubit in \(\ket{0}\) are those of \(-\ket{+}\).

import math

from qibo import Circuit, gates, get_backend
from qibo.models import qsvt_circuit, qsvt_phases

backend = get_backend()

# prepares |+> with amplitude 1/2 when the auxiliary qubit is in |0>
block_encoding = Circuit(2)
block_encoding.add(gates.RY(0, 2 * math.pi / 3))
block_encoding.add(gates.H(1))

# Chebyshev series of the polynomial, i.e. only the coefficient of T_3
phases = qsvt_phases([0.0, 0.0, 0.0, 1.0])
circuit = qsvt_circuit(block_encoding, phases, nancillas=1)

target = Circuit(1)
target.add(gates.H(0))

state = circuit().state()[:2]
print(backend.allclose(state, -target().state(), atol=1e-6))

True
Parameters:

  • block_encoding (qibo.models.circuit.Circuit) – circuit that implements \(U\). Its first nancillas qubits are the auxiliary qubits.

  • phases (ArrayLike) – phases of the polynomial, e.g. the output of qibo.models.qsvt_phases().

  • nancillas (int) – number \(a\) of auxiliary qubits of block_encoding.

Returns:

circuit with the signal qubit at position \(0\), followed by the qubits of block_encoding in the same order.

Return type:

qibo.models.circuit.Circuit

References

1. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC ‘19), 193-204 (2019).

Hamiltonian diagonalization#

Double-Bracket Iterations#

class qibo.models.DoubleBracketIteration(hamiltonian, backend=None)[source]#

Diagonalization double-bracket iteration (DBI) of a Hamiltonian.

Given a Hamiltonian \(H_{0}\), the \(k\)-th recursion step of the DBI is

\[H_{k+1} = e^{s_{k} \, W_{k}} \, H_{k} \, e^{-s_{k} \, W_{k}} \, , \quad W_{k} = [D_{k}, H_{k}] \, ,\]

where \(D_{k}\) is a diagonal operator and \(s_{k}\) is the step duration. If \(D_{k}\) is not specified, the dephasing \(\Delta(H_{k})\), i.e. the diagonal restriction of \(H_{k}\), is used. This choice, called canonical bracket, gives rise to the Głazek-Wilson-Wegner (GWW) DBI, which decreases the Hilbert-Schmidt norm of the off-diagonal restriction of \(H_{k}\) for sufficiently short durations.

Two types of rotation are available. In the "double_bracket" rotation, the exact unitary \(e^{-s_{k} \, W_{k}}\) is applied. In the "group_commutator" rotation, the unitary \(e^{i \sqrt{s_{k}} \, D_{k}} \, e^{i \sqrt{s_{k}} \, H_{k}} \, e^{-i \sqrt{s_{k}} \, D_{k}}\) is applied instead, which is the group commutator iteration (GCI) that can be implemented in a quantum computer through circuit(). A negative step_duration corresponds to flipping the sign of \(D_{k}\).

Parameters:

Example

from qibo.backends import NumpyBackend
from qibo.hamiltonians import TFIM
from qibo.models import DoubleBracketIteration

backend = NumpyBackend()

hamiltonian = TFIM(3, h=1.0, backend=backend)
dbi = DoubleBracketIteration(hamiltonian, backend=backend)
norms = dbi.run(nsteps=5)
print(norms[0] > norms[-1])

True

References

1. M. Gluza, Double-bracket quantum algorithms for diagonalization, Quantum 8, 1316 (2024).

property energy_fluctuations: ArrayLike#

sqrt{langle H_{k}^{2} rangle - langle H_{k} rangle^{2}} of the current Hamiltonian \(H_{k}\) in all computational basis states.

Fluctuations vanish for eigenstates of \(H_{k}\).

Type:

Energy fluctuations

Type:

math

property off_diagonal_norm: float#

Hilbert-Schmidt norm \(\|\sigma(H_{k})\|_{\text{HS}}\) of the off-diagonal restriction of the current Hamiltonian \(H_{k}\).

circuit(backend=None)[source]#

Circuit \(V_{K}\) of the group commutator iteration (GCI) after \(K\) steps.

The circuit is built recursively from the recorded step durations \(s_{k}\) and diagonal operators \(D_{k}\) as

\[V_{k+1} = V_{k} \, e^{i \sqrt{s_{k}} \, D_{k}} \, V_{k}^{\dagger} \, e^{i \sqrt{s_{k}} \, H_{0}} \, V_{k} \, e^{-i \sqrt{s_{k}} \, D_{k}} \, ,\]

with \(V_{0} = \mathbb{1}\), so that \(H_{K} = V_{K}^{\dagger} \, H_{0} \, V_{K}\) and \(V_{K} |\mu\rangle\) approximates an eigenstate of \(H_{0}\) for a computational basis state \(|\mu\rangle\). It only contains evolutions under \(H_{0}\) and under the diagonal operators, and its number of evolutions under \(H_{0}\) is \((3^{K} - 1) / 2\). It reproduces the iteration exactly, and therefore is only available when the "group_commutator" rotation was used in all steps.

Parameters:

backend (qibo.backends.abstract.Backend, optional) – backend used to build the evolution gates. If None, it uses the backend of the iteration. Defaults to None.

Returns:

Circuit implementing \(V_{K}\).

Return type:

qibo.models.circuit.Circuit

Raises:

ValueError – If the dimension of the Hamiltonian is not a power of two, or if any step of the iteration did not use the "group_commutator" rotation.

optimize_step(diagonal=None, rotation='double_bracket', step_max=None, nsamples=100)[source]#

Step duration that maximally decreases the off-diagonal norm in one step.

A grid search over \([-s_{\max}, s_{\max}]\) (\([0, s_{\max}]\) for the canonical bracket) is followed by a bounded local refinement around the best point.

Parameters:

  • diagonal (ArrayLike, optional) – diagonal operator \(D_{k}\), given either as the vector of its real diagonal entries or as a real diagonal matrix. If None, the dephasing of the current Hamiltonian is used. Defaults to None.

  • rotation (str, optional) – either "double_bracket" or "group_commutator". Defaults to "double_bracket".

  • step_max (float, optional) – upper limit of the search. If None, it is set to \(\pi / \|[D_{k}, H_{k}]\|\), with the operator norm. Defaults to None.

  • nsamples (int, optional) – number of points of the grid search. Defaults to \(100\).

Returns:

Optimal step duration.

Return type:

float

run(nsteps, diagonals=None, rotation='double_bracket', step_max=None, nsamples=100)[source]#

Runs nsteps greedy recursion steps of the iteration.

In each step, the step duration is optimized for the canonical bracket and for each diagonal operator in diagonals, and the choice yielding the smallest off-diagonal norm is applied.

Parameters:

  • nsteps (int) – number of recursion steps.

  • diagonals (list[ArrayLike], optional) – candidate real diagonal operators \(D_{k}\), e.g. products of Pauli-\(Z\) operators, to be considered in addition to the canonical bracket in every step. Defaults to None.

  • rotation (str, optional) – either "double_bracket" or "group_commutator". Defaults to "double_bracket".

  • step_max (float, optional) – see optimize_step(). Defaults to None.

  • nsamples (int, optional) – see optimize_step(). Defaults to \(100\).

Returns:

Off-diagonal norms before the first step and after each step.

Return type:

list[float]

step(step_duration, diagonal=None, rotation='double_bracket')[source]#

Performs one recursion step and updates the iterated Hamiltonian.

Parameters:

  • step_duration (float) – step duration \(s_{k}\).

  • diagonal (ArrayLike, optional) – diagonal operator \(D_{k}\), given either as the vector of its real diagonal entries or as a real diagonal matrix. If None, the dephasing of the current Hamiltonian is used. Defaults to None.

  • rotation (str, optional) – either "double_bracket" or "group_commutator". Defaults to "double_bracket".

Returns:

Iterated Hamiltonian \(H_{k+1}\).

Return type:

ArrayLike