SQA computing

Qaptiva is equipped with a simulated quantum annealer (SQA), which can solve combinatorial optimization problems encoded in an Ising or Quadratic Unconstrained Binary Optimization (QUBO) formalism - take a look at an Introductory notebook. It can also handle a general Combinatorial Problem with clauses and variables, as long as each of its Clause contains no more than two Var, such that it is translatable to Ising or QUBO.

The SQA solver is inside the class SQAQPU which receives a Job created via the to_job() method of the special purpose Ising or QUBO classes (or CombinatorialProblem, if applicable).

Inner workings

SQA is built upon a heuristic which aims to minimize quantum Ising Hamiltonians.

The questions of whether SQA performs such minimizations more efficiently than physical quantum annealing machines, and whether SQA can be called ‘emulation’ of those machines is still under scientific discussion with some more recent advances being [KonzLKT21], [BN21], [KRL21], along with [RonnowWJ+14], [DBI+16], [HJA+15] or [AA17], for instance.

Formally, our SQA implementation is based on a discrete-time path integral Monte Carlo formulation of quantum annealing, as derived in [MartovnakST02].

In short, instead of sampling the equilibrium distribution, at finite temperature of the quantum Ising Hamiltonian:

\[H = -\sum_{i,j} J_{i,j}\sigma_{z}^{i}\sigma_{z}^{j}-\sum_{i} h_{i}\sigma_{z}^{i} - \Gamma\sum_{i}\sigma_{x}^{i}\]

one samples from the equivalent classical Ising Hamiltonian:

\[H = -\sum_{k=1}^{n_{trotters}}\left( \sum_{i,j} J_{i,j} s_{i}^{k}s_{j}^{k} + \sum_{i} h_{i} s_{i}^{k} + J^{\perp}s_{l}^{k}s_{l}^{k+1} \right)\]

with \(J^{\perp} = - \frac{n_{trotters}T}{2}\cdot \log\left(\tanh(\frac{\Gamma}{n_{trotters}T})\right)\) and \(n\) quantum spins are replaced with \(n_{trotters}\times n\) classical spins.

In quantum annealing, \(\Gamma\) is typically gradually decreased from a high value to \(0\), such that, if the system is prepared in the ground state of \(\sum_{i}\Gamma\sigma_{x}^{i}\), it ends up in the ground state of the Ising Hamiltonian at the end of the transition.

The idea of simulated quantum annealing is to sample from the equilibrium distribution of the equivalent classical Hamiltonian at several points \(\{\Gamma_{l}\}\) along that transition. The configuration resulting from sampling at \(\Gamma_{l}\) is kept at the starting configuration for \(\Gamma_{l+1}\).

The following picture describes in pseudo-code how SQA works.

../../../_images/simulated_quantum_annealing_algoritm_latex.png

Note

The quality of the solutions returned by SQA will depend on the parameters given to the algorithm (minimum and maximum gamma and temperature, number of Monte Carlo steps, etc).
The memory requirements of simulated quantum annealing are polynomial in the number of spins. There is no hard memory limit as to how many spins can be represented and manipulated with this technique.

Bibliography

AA17: Evgeny Andriyash and Mohammad H Amin. Can quantum monte carlo simulate quantum annealing? 2017. arXiv:1703.09277.
BN21: Yuki Bando and Hidetoshi Nishimori. Simulated quantum annealing as a simulator of nonequilibrium quantum dynamics. Physical Review A, 104(2):022607, 2021. URL: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.104.022607.
DBI+16: Vasil S Denchev, Sergio Boixo, Sergei V Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven. What is the computational value of finite-range tunneling? Physical Review X, 6(3):031015, 2016. URL: https://journals.aps.org/prx/abstract/10.1103/PhysRevX.6.031015.
HJA+15: Itay Hen, Joshua Job, Tameem Albash, Troels F Rønnow, Matthias Troyer, and Daniel A Lidar. Probing for quantum speedup in spin-glass problems with planted solutions. Physical Review A, 92(4):042325, 2015. URL: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.92.042325.
KonzLKT21: Mario S. K"onz, Wolfgang Lechner, Helmut G. Katzgraber, and Matthias Troyer. Embedding overhead scaling of optimization problems in quantum annealing. Physical Review X Quantum, 2(4):042325, 2021. URL: https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.2.040322.
KRL21: A.D. King, Jack Raymond, and Trevor et al. Lanting. Scaling advantage over path-integral monte carlo in quantum simulation of geometrically frustrated magnets. Nature Communications, 12:1113, 2021. URL: https://www.nature.com/articles/s41467-021-20901-5.
MartovnakST02: Roman Martoňák, Giuseppe E Santoro, and Erio Tosatti. Quantum annealing by the path-integral monte carlo method: the two-dimensional random ising model. Physical Review B, 66(9):094203, 2002. URL: https://journals.aps.org/prb/abstract/10.1103/PhysRevB.66.094203.
RonnowWJ+14: Troels F Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V Isakov, David Wecker, John M Martinis, Daniel A Lidar, and Matthias Troyer. Defining and detecting quantum speedup. science, 345(6195):420–424, 2014. URL: https://science.sciencemag.org/content/345/6195/420.full.