Fermionic Quantum Approximate Optimization Algorithm

Abstract

Quantum computers are expected to accelerate solving combinatorial optimization problems, including algorithms such as Grover adaptive search and quantum approximate optimization algorithm (QAOA). However, many combinatorial optimization problems involve constraints which, when imposed as soft constraints in the cost function, can negatively impact the performance of the optimization algorithm. In this paper, we propose fermionic quantum approximate optimization algorithm (FQAOA) for solving combinatorial optimization problems with constraints. Specifically FQAOA tackle the constrains issue by using fermion particle number preservation to intrinsically impose them throughout QAOA. We provide a systematic guideline for designing the driver Hamiltonian for a given problem Hamiltonian with constraints. The initial state can be chosen to be a superposition of states satisfying the constraint and the ground state of the driver Hamiltonian. This property is important since FQAOA reduced to quantum adiabatic computation in the large limit of circuit depth p and improved performance, even for shallow circuits with optimizing the parameters starting from the fixed-angle determined by Trotterized quantum adiabatic evolution. We perform an extensive numerical simulation and demonstrates that proposed FQAOA provides substantial performance advantage against existing approaches in portfolio optimization problems. Furthermore, the Hamiltonian design guideline is useful not only for QAOA, but also Grover adaptive search and quantum phase estimation to solve combinatorial optimization problems with constraints. Since software tools for fermionic systems have been developed in quantum computational chemistry both for noisy intermediate-scale quantum computers and fault-tolerant quantum computers, FQAOA allows us to apply these tools for constrained combinatorial optimization problems.

arXiv commentAccepted for publication in Physical Review Research on March 29, 2023. 16 pages, 8 figures

References in corpus (28)

• Quantum Annealing in the Transverse Ising Model
• Quantum Circuit Learning
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Hartree-Fock on a superconducting qubit quantum computer
• Towards Practical Quantum Variational Algorithms
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Qulacs: a fast and versatile quantum circuit simulator for research purpose
• Quantum computing for energy systems optimization: Challenges and opportunities
• Solving strongly correlated electron models on a quantum computer
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• Warm-starting quantum optimization
• Low Depth Quantum Simulation of Electronic Structure
• $XY$-mixers: analytical and numerical results for QAOA
• Strategies for solving the Fermi-Hubbard model on near-term quantum computers
• Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
• Quantum circuits for strongly correlated quantum systems
• Quantum algorithms to simulate many-body physics of correlated fermions
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Residual Energies after Slow Quantum Annealing
• Dissipation in adiabatic quantum computers: Lessons from an exactly solvable model
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Constrained quantum annealing of graph coloring
• Analytical Framework for Quantum Alternating Operator Ansätze
• Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
• Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad

Cited by in corpus (8)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Quantum Speedup of the Dispersion and Codebook Design Problems
• Simulation of a feedback-based algorithm for quantum optimization for a realistic neutral atom system with an optimized small-angle controlled-phase gate
• Experimental Demonstration of Fermionic QAOA with One-Dimensional Cyclic Driver Hamiltonian
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Electric Power Demand Portfolio Optimization by Fermionic QAOA with Self-Consistent Local Field Modulation