BACKGROUND

Quantum computers promise to solve industry-critical problems which are otherwise unsolvable or only very inefficiently addressable using classical computers. Key application areas include chemistry and materials, bioscience and bioinformatics, logistics, and finance. Interest in quantum computing has recently surged, in part due to a wave of advances in the performance of ready-to-use quantum computers.

Optimization problems, including solving systems of linear equations, eigenvalue problems, and constrained minimization of cost functions, are the key component of many science and engineering applications. Classical methods for numerical solution of optimization problems are well developed but suffer from the curse of dimensionality; that is, conventional systems typically perform sub-optimally when the problem size increases.

An emerging genre of algorithms in the space of quantum computing is hybrid quantum-classical algorithms, where a parametrized quantum circuit is used for solving a certain task using a quantum computer and where a classical computer is used for optimizing the quantum circuit parameters with respect to some objective function that is efficiently measurable on the quantum computer.

However, one potential challenge in implementing hybrid quantum-classical algorithms effectively concerns optimizing the quantum circuit. As the problem size of a task grows, the number of parameters that need to be optimized also grows, giving rise to high-dimensional black-box optimization problems that are difficult for a classical computer to solve. Such difficulty is rigorously manifested in a recent study (McClean et al., 2018) showing that the optimization landscape has vanishingly small gradient in most regions. To surmount the problem, one known potential solution (McClean et al., 2016) is to start from an educated initial guess of a good quantum circuit for the problem instead of a quantum circuit chosen in a random or ad hoc manner.

Quantum computers provide alternative means of solving the optimization problems by taking advantage of unique features of quantum mechanics that are not accessible by classical computers. One well-known method for solving eigenvalue problems on a quantum computer is phase estimation. Assuming that one can start with a quantum state encoding a reasonably good approximation of the eigenvector sought, phase estimation can generate a quantum state encoding the exact eigenstate sought as well as the corresponding eigenvalue up to certain error.

Another well-known technique for solving eigenvalue problems on quantum computers is the variational quantum eigensolver (VQE). As a hybrid quantum-classical algorithm, VQE prepares a quantum state with a quantum circuit with tunable parameters. The approximate ground state (lowest eigenvector) and ground state energy are obtained by tuning the parameters of the quantum circuit while measuring the energy of the state with respect to the Hamiltonian (the Hermitian matrix whose lowest eigenpair is sought).

However, both the phase estimation and VQE rely on unitary transformations of the initial quantum state to generate the desired output state. The unitary transformations can be implemented on a quantum computer. However, such methods relying on unitary operations are dependent on a good initial approximation to the true solution to the optimization problem—but good initial approximations are rarely known in most practical scenarios, limiting the use of techniques relying on unitary transformations.

Furthermore, in some conventional approaches, the initial approximation to the solution is subject to restrictive assumptions that the distance between the initial approximation and the exact solution of the optimization problem is sufficiently small, in order to enable fast convergence. One reason for possibly slow convergence is that the optimization method is restricted to unitary transformations on the quantum computer part of the hybrid quantum-classical computer, due to the nature of closed quantum system evolution. Such restrictions on the initial approximation being sufficiently close to the solution cannot be met in many practical applications, significantly limiting the use of quantum computing.

SUMMARY

A hybrid quantum-classical computing method for solving optimization problems though applications of non-unitary transformations. An initial state is prepared, a transformation is applied, and the state is updated to provide an improved answer. This update procedure is iterated until convergence to an approximately optimal solution.

