  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.
