Fermionic Quantum Approximate Optimization Algorithm

• URL: http://arxiv.org/abs/2301.10756v3
• Date: Sun, 30 Apr 2023 05:38:39 GMT
• Title: Fermionic Quantum Approximate Optimization Algorithm
• Authors: Takuya Yoshioka, Keita Sasada, Yuichiro Nakano, and Keisuke Fujii
• Abstract summary: We propose fermionic quantum approximate optimization algorithm (FQAOA) for solving optimization problems with constraints. 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.
• Score: 11.00442581946026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Adaptive quantum optimization algorithms for programmable atom-cavity systems [6.508793834090864]
  We show cold atoms in an optical cavity can be built as a universal quantum with programmable all-to-all interactions. We find the success probability of the standard quantum approximate algorithm (QAOA) decays rapidly with the problem size. Inspired by the counterdiabatic driving, we propose an adaptive ansatz of QAOA which releases the parameter freedom of the NPP Hamiltonian to match higher-order counterdiabatic terms.
  arXiv  Detail & Related papers  (2024-06-11T08:37:31Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
  Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent Ising model suitable for the quantum device. We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Prog-QAOA.
  arXiv  Detail & Related papers  (2022-09-07T18:01:01Z)
• How Much Entanglement Do Quantum Optimization Algorithms Require? [0.0]
  We study the entanglement generated during the execution of ADAPT-QAOA. By incrementally restricting this flexibility, we find that a larger amount of entanglement entropy at earlier stages coincides with faster convergence at later stages.
  arXiv  Detail & Related papers  (2022-05-24T18:00:02Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits [15.279642278652654]
  We present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits. Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.
  arXiv  Detail & Related papers  (2021-12-21T12:41:31Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
  arXiv  Detail & Related papers  (2021-05-14T11:31:14Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.