qat.opt.MixingFactory

class qat.opt.MixingFactory

A factory to define problem independent mixing Hamiltonians (i.e. initial Hamiltonians in adiabatic quantum optimization schedules).

All methods generate object implementing the InitialStateBuilder interface and returns a pair (such an object, mixing Hamiltonian).

static bit_flip(nbits, restrict_to=None)

Builds a bit flip mixing Hamiltonian:

\[H_0 = - \sum \sigma_x\]

Its ground state is the product state:

\[|\psi_0\rangle = |+\rangle ^ {\otimes n}\]

and is returned in string format.

This is the standard Hamiltonian for most applications.

Parameters
  • nbits (int) – the number of qubits in the system

  • restrict_to (optional, list<int>) – a possible list of qubits to restrict the mixing to. If set, the sum over \(\sigma_x\) is restricted to these qubits. The initial state of other qubits will be set to \(|0\rangle\).

Returns

a pair (structure preparing the initial state, mixing Hamiltonian).

Return type

(SimpleInitialState, Observable)

static bit_move(nbits, hamming_weight, exact=True, tmax_psi_0=50.0)

Builds a bit move mixing Hamiltonian that preserves Hamming weight:

\[H_0 = - \sum_{i, j} S_{i, j}\]

where \(S_{i,j}\) is the following two qubits operator located on qubits \(i, j\):

\[S_{i, j} = \frac{\sigma_y\otimes\sigma_y + \sigma_x\otimes\sigma_x}{2}\]

The main purpose of this mixing is to explore subset of bitstrings of constant Hamming weight. In that regard, it is important to start from an appropriate initial state that corresponds to the ground state of \(H_0\) restricted to the classical states of fixed Hamming weight \(k\).

This ground state is the equi-superposition of classical states of Hamming weight \(k\):

\[|\psi_0\rangle = {n \choose k}^{-\frac{1}{2}} \sum_{x} |x\rangle\]

where the sum ranges over all bit-strings \(x\) of Hamming weight \(k\).

When using a simulator, one can prepare this state using a numpy array (which is fine for small number of qubits).

In real use cases, it is possible to approximate this state by performing a problem independent adiabatic quantum optimization using:

\[ \begin{align}\begin{aligned}H'_0 = - \sum_i \sigma_x^i\\|\psi'_0\rangle = |+\rangle ^{\otimes n}\end{aligned}\end{align} \]

and

\[H'_1 = \left(\sum_i \frac{1 - \sigma_z^i}{2} - k\right)^2\]

The ground state of \(H'_1\) is exactly the state \(|\psi_0\rangle\). Moreover, it is argued in [CFGG00] that the min-gap of this evolution is located close to the end of the evolution and that its width is a \(O(\frac{1}{T})\). In particular, this entails that one can pick a polynomially large \(T\) and be sure to build a large overlap between the state of our system and the perfect \(|\psi_0\rangle\).

Parameters
  • nbits (int) – the number of qubits in the system

  • hamming_weight (int) – the Hamming weight of the bit strings to mix

  • exact (optional, bool) – if set to True, the initial state will be described using a numpy array (which is not a scalable solution, but is faster and simpler for small systems).

  • tmax_psi_0 (optional, float) – the tmax for the first AQO (in the case of an inexact preparation). Default to 50.

Example:

from qat.opt import MixingFactory

# Mixes bit-strings of length 10 and Hamming weight 5
# This generates a numpy array of length 2^10 to describe the initial state (be careful :))
mixing = MixingFactory.bit_move(10, 5)
# Mixes bit-strings of length 10 and Hamming weight 5
# and prepares the initial state via a problem independent AQO
mixing = MixingFactory.bit_move(10, 5, exact=False)
# Mixes bit-strings of length 10 and Hamming weight 5
# and prepares the initial state via a problem independent AQO
# of duration 70
mixing = MixingFactory.bit_move(10, 5, exact=False, tmax_psi_0=70)
Returns

a pair (structure preparing the initial state, mixing Hamiltonian). The return type of the first entry depends on the exact parameter.

Return type

(SimpleInitialState/IndependentAQO, Observable)

References

CFGG00

Andrew M Childs, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. Finding cliques by quantum adiabatic evolution. arXiv preprint quant-ph/0012104, 2000.