Approximating under the Influence of Quantum Noise and Compute Power

• URL: http://arxiv.org/abs/2408.02287v1
• Date: Mon, 5 Aug 2024 07:48:49 GMT
• Title: Approximating under the Influence of Quantum Noise and Compute Power
• Authors: Simon Thelen, Hila Safi, Wolfgang Mauerer,
• Abstract summary: The quantum approximate optimisation algorithm (QAOA) is at the core of many scenarios that aim to combine the power of quantum computers and classical high-performance computing appliances for optimisation. We study factors that affect solution quality and temporal behaviour of four QAOA variants using comprehensive density-matrix-based simulations. Our results, accompanied by a comprehensive reproduction package, show strong differences between QAOA variants that can be pinpointed to narrow and specific effects.
• Score: 3.0302054726041017
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum approximate optimisation algorithm (QAOA) is at the core of many scenarios that aim to combine the power of quantum computers and classical high-performance computing appliances for combinatorial optimisation. Several obstacles challenge concrete benefits now and in the foreseeable future: Imperfections quickly degrade algorithmic performance below practical utility; overheads arising from alternating between classical and quantum primitives can counter any advantage; and the choice of parameters or algorithmic variant can substantially influence runtime and result quality. Selecting the optimal combination is a non-trivial issue, as it not only depends on user requirements, but also on details of the hardware and software stack. Appropriate automation can lift the burden of choosing optimal combinations for end-users: They should not be required to understand technicalities like differences between QAOA variants, required number of QAOA layers, or necessary measurement samples. Yet, they should receive best-possible satisfaction of their non-functional requirements, be it performance or other. We determine factors that affect solution quality and temporal behaviour of four QAOA variants using comprehensive density-matrix-based simulations targeting three widely studied optimisation problems. Our simulations consider ideal quantum computation, and a continuum of scenarios troubled by realistic imperfections. Our quantitative results, accompanied by a comprehensive reproduction package, show strong differences between QAOA variants that can be pinpointed to narrow and specific effects. We identify influential co-variables and relevant non-functional quality goals that, we argue, mark the relevant ingredients for designing appropriate software engineering abstraction mechanisms and automated tool-chains for devising quantum solutions from high-level problem specifications.

Related papers

• Connecting the Hamiltonian structure to the QAOA performance and energy landscape [0.0]
  Quantum Alternating Operator Ansatz (QAOA) is effective for solving Quadratic Unconstrained Binary Optimization problems. This study emphasizes the algorithm's robustness and potential for optimization tasks on near-term quantum devices.
  arXiv  Detail & Related papers  (2024-07-05T11:32:46Z)
• Solving Combinatorial Optimization Problems with a Block Encoding Quantum Optimizer [0.0]
  Block ENcoding Quantum (BEQO) is a hybrid quantum solver that uses block encoding to represent the cost function. Our findings confirm that BENQO performs significantly better than QAOA and competes with VQE across a variety of performance metrics.
  arXiv  Detail & Related papers  (2024-04-22T10:10:29Z)
• 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)
• Benchmarking Metaheuristic-Integrated QAOA against Quantum Annealing [0.0]
  The study provides insights into the strengths and limitations of both Quantum Annealing and metaheuristic-integrated QAOA across different problem domains. The findings suggest that the hybrid approach can leverage classical optimization strategies to enhance the solution quality and convergence speed of QAOA.
  arXiv  Detail & Related papers  (2023-09-28T18:55:22Z)
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem [0.0]
  We discuss the Capacitated Vehicle Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP) Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically. Quantum computing may offer a way to improve the time to solution.
  arXiv  Detail & Related papers  (2023-04-19T13:03:50Z)
• Fermionic Quantum Approximate Optimization Algorithm [11.00442581946026]
  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.
  arXiv  Detail & Related papers  (2023-01-25T18:36:58Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  Energy systems optimization problems are complex due to strongly non-linear system behavior and multiple competing objectives. In some cases, proposed optimal solutions need to obey explicit input constraints related to physical properties or safety-critical operating conditions. This paper proposes a novel data-driven strategy using tree ensembles for constrained multi-objective optimization of black-box problems.
  arXiv  Detail & Related papers  (2021-11-04T20:18:55Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• 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)
• 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.