Skip to content

Quantum Algorithms

So far, the guide has explained the various ways in which the user may interact with the optimization package. Here we explain the actual process implemented by the optimization engine. Namely, the algorithms used, the way they are applied, and the degrees of freedom available to the user.

The optimization platform implements hybrid quantum-classical optimization algorithms. These algorithms were developed to fit NISQ-era quantum computers with limited quantum resources. The algorithms may be divided to two parts. First, a quantum circuit referred to as an "ansatz", which is a variational parametrized quantum circuit encoding possible problem solutions. Second, is a classical optimization procedure. Two of the most recognized algorithms are VQE (Variational Quantum Eigensolver) [1] and QAOA (Quantum Approximate Optimization Algorithm) [2] . Both have been extensively studied in the last decade and show great promise for the near future [3] .

Specifically, the package focuses on a new variant of QAOA with the same name acronym: Quantum Alternating Optimization Ansatz [4] . This algorithm enables the restriction of the search process to a subspace of the entire Hilbert space, corresponding to solutions which satisfy the problem’s constraints. This reduces the effective search space by many orders of magnitude, and may enhance the search performance. The Classiq platform allows the analysis and embedding of problem constraints in two modes.

  1. Original QAOA (Quantum Approximate Optimization Algorithm). Here the constraints are expressed as penalty terms in the objective function. The optimization process will discourage solutions that don’t obey the constraints. The search space spans over the entire Hilbert space and the algorithm mixes all the possible solutions. To select this algorithm, set qaoa_preferences.qsolver = Qsolve.QAOAPenalty. The conversion method from constraints to penalty terms is described in [5] .

  2. New QAOA (Quantum Alternating Optimization Ansatz). This algorithm explicitly constrains the search space in accordance with the problem constraints. The constraints are embedded in the initialization and mixer layers. To select this algorithm, set qaoa_preferences.qsolver = Qsolve.QAOAMixer.

References

[1] A. Peruzzo, et al., A variational eigenvalue solver on a quantum processor, Nature comm. 5, 4213, (2014)

[2] E. Farhi, et al., A Quantum Approximate Optimization Algorithm, arxiv:quant-ph/1411.4028, (2014)

[3] K. Bharti, et al., Noisy intermediate-scale quantum (NISQ) algorithms, arxiv:quant-ph/2101.08448, (2021)

[4] S. Hadfield, et al., From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz, Algorithms 12(2), 34, (2017)

[5] A. Lucas,Ising formulations of many np problems, Frontiers in Physics, 2:5, (2014)