Quantum Payment Optimization Chapter 3 -Approaches to Optimization
Combinatorial optimization problems involve finding an optimal solution in a large but finite set of solutions. They are closely related to integer programming and often best visualized as optimizing networked graph structures. Well-known examples include the traveling salesman, knapsack problems, and minimum spanning tree problem. Their decision variables can be discrete or binary, and they are non-convex and not solvable in polynomial time classically.
Quadratic unconstrained binary optimizations (QUBOs) are a broad class of combinatorial problems that belong to NP-hard problems – meaning optimal solutions using exact solvers won't work for large problems. They are an unconstrained model except for the requirements on decision variables. The equality constraints are added to the objective function as a quadratic penalization term in an augmented Lagrangian fashion. The same penalty can be used for all constraints or different if there are hard and soft constraints. (soft constraints - where slight violations can be tolerated). Programs are generally used (or written) to expand the quadratic equation, determine the coefficients, and rewrite them in matrix form to be evaluated by a solver.
The NP-hard nature of these problems means as the size of the scale of the problem they quickly become unsolvable in a reasonable amount of time. Classical exact solvers exist to solve limited combinatorial problems. There are commercial solvers like IBMs CPLEX optimizer or Gurobi, which can use thousands of constraints and variables and help efficiently use resources, or open-source solvers used primarily for research such as SCIP.
For large problems, heuristics are used and result in a solution that is not guaranteed to be optimal. For this reason, quantum computation has received a lot of attention. Problems thought intractable on a classical computer could be tractable in a quantum computer in at least bounded-error polynomial time. Quantum annealing from Dwave has already resulted in a speedup in finding solutions to some of these problems and has produced quantum-inspired algorithms such as Fujitsu digital annealer and Toshiba's simulated bifurcation machine.
Since large fault-tolerant quantum computers are not a reality, another approach is to tackle combinatorial optimization problems is to use a quantum-classical hybrid model. Variational Quantum Eigenstates (VQE) is one such model. VQE is an approach used for noisy intermediate state computing (NISC). The quantum computer is only used to determine the energy (eigenvalues) for a few parameters. The classical computer then optimizes parameters and determines the new parameterized wavefunction (ansatz) to feedback to the loop. Essentially, it chooses a parametrization of the space of quantum states and uses classical optimization to determine the values of the quantum state's parameters that minimize or maximize an objective function.
The objective function is given by the Hamiltonian, encoding the total energy of the system. The variational theorem states that the expectation value of the Hamiltonian is greater or equal to the minimum eigenvalue of the Hamiltonian, generally the ground state, and that will correspond to the minimum of the objective function. If the Hamiltonian can encode the objective function of the optimization problem, we can apply the variational approach. The steps for a VQE are as follows:
1. Convert optimization problem into Ising Hamiltonian
2. Quantum: compute information about the energy (eigenvalue) of the system
Parameterize the quantum state with a small set of rotation parameters (Ω)
each Ω state is expressed as a parameterized quantum circuit applied to the initial state |0>
3. Classical: update parameters
Compare eigenvalue with previous one (find gradient)
Select new parameters, Ω, such that the energy of the system is minimized
4.
Repeat 2 and 3
Return minimum eigenvalue and eigen vector
The quantum approximation optimization algorithm (QAOA), also known as the Quantum alternating operator ansatz, is another quantum approach for solving combinatorial optimizations similar to the VQE. It's an approximation algorithm delivering the best result characterized by the lower bound of the desired approximation ratio. Introduced by Farhi et al. in 2014, QAOA beat the best classical algorithm but was then overtaken. Nevertheless, QAOA is a candidate to show quantum supremacy - If its lowest depth can be efficiently simulated classically, then P = NP. Moreover, it is used to find non-trivial quantum states like the ground state or Greenberger-Horne_Zeilinger (GHZ) state.
QAOA Encodes the objective function by converting it to an Ising Hamiltonian Ha. A mixing Hamiltonian Hb is added to avoid getting stuck in a local minimum. The Ha and Hb are alternately applied to the initialized quantum processor to generate a variational wavefunction. Similar to VQE, the expectation value of Ha is found for this variational state by repeatedly measuring the quantum state and optimizing the parameters, and maximizing the measurement output.
The application of quantum to combinatorial optimization problems has delivered a speedup in the time needed to find a solution. As quantum continues to develop, increasing the number of qubits and reducing the noise, further improvements with respect to problem size and speed will be realized. However, one of the most exciting developments in this area has been how quantum has inspired new algorithms used to extend classical computers' performance. It will be interesting to see where the new constraints for solving these problems lie in the future.