Fermionic Quantum Approximate Optimization Algorithm
arXiv:2301.10756 · doi:10.1103/PhysRevResearch.5.023071
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.
Accepted for publication in Physical Review Research on March 29, 2023. 16 pages, 8 figures
References in corpus (4)
- Quantum computing for energy systems optimization: Challenges and opportunities
- Quantum circuits for strongly correlated quantum systems
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
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