Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem

Abstract

Optimization problems in finance, physics and computer science are typically very hard to tackle in classical computing and quantum computing could help speed up computations and provide efficient methods for tackling large problems. Typically, to treat the problem with a quantum computer, the optimal solution is cast as the ground state of a diagonal Hamiltonian. We develop a new method, called ITE-BE, based on a recent imaginary time algorithm, which requires no variational parameter optimization as all parameters can be derived analytically from the target Hamiltonian. We also demonstrate that our method can be successfully combined with other quantum algorithms such as quantum approximate optimization algorithm (QAOA). For illustration, here we study the MaxCut problem. We find that the QAOA ansatz increases the post-selection success of ITE-BE, and shallow QAOA circuits, when boosted with ITE-BE, achieve better performance than deeper QAOA circuits. For the special case of the transverse initial state, we adapt our block encoding scheme to allow for a deterministic application of the first layer of the circuit.

12 pages, 7 figures

References in corpus (26)

• Ising formulations of many NP problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Variational ansatz-based quantum simulation of imaginary time evolution
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Training variational quantum algorithms is NP-hard
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Challenges and Opportunities in Quantum Optimization
• How Powerful is Adiabatic Quantum Computation?
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Auxiliary field diffusion Monte Carlo calculations of light and medium-mass nuclei with local chiral interactions
• Training A Quantum Optimizer
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Imaginary Time Propagation on a Quantum Chip
• Auxiliary Field Diffusion Monte Carlo calculation of ground state properties of neutron drops
• Variational Quantum Time Evolution without the Quantum Geometric Tensor
• Fast Simulation of High-Depth QAOA Circuits
• BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints
• Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity
• QAOA with $N\cdot p\ge 200$
• Exact block encoding of imaginary time evolution with universal quantum neural networks

Cited by in corpus (1)

• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations