Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization

Abstract

Constrained binary optimization aims to find an optimal assignment to minimize or maximize the objective meanwhile satisfying the constraints, which is a representative NP problem in various domains, including transportation, scheduling, and economy. Quantum approximate optimization algorithms (QAOA) provide a promising methodology for solving this problem by exploiting the parallelism of quantum entanglement. However, existing QAOA approaches based on penalty-term or Hamiltonian simulation fail to thoroughly encode the constraints, leading to extremely low success rate and long searching latency. This paper proposes Choco-Q, a formal and universal framework for constrained binary optimization problems, which comprehensively covers all constraints and exhibits high deployability for current quantum devices. The main innovation of Choco-Q is to embed the commute Hamiltonian as the driver Hamiltonian, resulting in a much more general encoding formulation that can deal with arbitrary linear constraints. Leveraging the arithmetic features of commute Hamiltonian, we propose three optimization techniques to squeeze the overall circuit complexity, including Hamiltonian serialization, equivalent decomposition, and variable elimination. The serialization mechanism transforms the original Hamiltonian into smaller ones. Our decomposition methods only take linear time complexity, achieving end-to-end acceleration. Experiments demonstrate that Choco-Q shows more than 235$\times$ algorithmic improvement in successfully finding the optimal solution, and achieves 4.69$\times$ end-to-end acceleration, compared to prior QAOA designs.

14 pages, 14 figures, conference

References in corpus (16)

• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Grover Algorithm with zero theoretical failure rate
• Training variational quantum algorithms is NP-hard
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Efficient synthesis of universal Repeat-Until-Success circuits
• Benchmarking the performance of portfolio optimization with QAOA
• Quantum annealing: the fastest route to quantum computation?
• Penalty Weights in QUBO Formulations: Permutation Problems
• Synthesizing Quantum-Circuit Optimizers
• Red-QAOA: Efficient Variational Optimization through Circuit Reduction
• Probabilistic unitary synthesis with optimal accuracy
• Recursive Methods for Synthesizing Permutations on Limited-Connectivity Quantum Computers
• Experimental Demonstration of Fermionic QAOA with One-Dimensional Cyclic Driver Hamiltonian