Qubit-efficient quantum combinatorial optimization solver

• URL: http://arxiv.org/abs/2407.15539v1
• Date: Mon, 22 Jul 2024 11:02:13 GMT
• Title: Qubit-efficient quantum combinatorial optimization solver
• Authors: Bhuvanesh Sundar, Maxime Dupont,
• Abstract summary: We develop a qubit-efficient algorithm that overcomes the limitation by mapping a candidate bit solution to an entangled wave function of fewer qubits. This approach could benefit near-term intermediate-scale and future fault-tolerant small-scale quantum devices.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum optimization solvers typically rely on one-variable-to-one-qubit mapping. However, the low qubit count on current quantum computers is a major obstacle in competing against classical methods. Here, we develop a qubit-efficient algorithm that overcomes this limitation by mapping a candidate bit string solution to an entangled wave function of fewer qubits. We propose a variational quantum circuit generalizing the quantum approximate optimization ansatz (QAOA). Extremizing the ansatz for Sherrington-Kirkpatrick spin glass problems, we show valuable properties such as the concentration of ansatz parameters and derive performance guarantees. This approach could benefit near-term intermediate-scale and future fault-tolerant small-scale quantum devices.

Related papers

• Symmetry-preserved cost functions for variational quantum eigensolver [0.0]
  Hybrid quantum-classical variational algorithms are considered ideal for noisy quantum computers. We propose encoding symmetry preservation directly into the cost function, enabling more efficient use of Hardware-Efficient Ans"atze.
  arXiv  Detail & Related papers  (2024-11-25T20:33:47Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer [13.528362112761805]
  We show the largest-to-date execution of a quantum optimization algorithm that preserves constraints on quantum hardware. We execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159. We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.
  arXiv  Detail & Related papers  (2022-06-13T16:21:04Z)
• Adiabatic quantum computing with parameterized quantum circuits [0.0]
  We propose a discrete version of adiabatic quantum computing that can be implemented in a near-term device. We compare our proposed algorithm with the Variational Quantum Eigensolver on two classical optimization problems.
  arXiv  Detail & Related papers  (2022-06-09T09:31:57Z)
• Surviving The Barren Plateau in Variational Quantum Circuits with Bayesian Learning Initialization [0.0]
  Variational quantum-classical hybrid algorithms are seen as a promising strategy for solving practical problems on quantum computers in the near term. Here, we introduce the fast-and-slow algorithm, which uses gradients to identify a promising region in Bayesian space. Our results move variational quantum algorithms closer to their envisioned applications in quantum chemistry, optimization, and quantum simulation problems.
  arXiv  Detail & Related papers  (2022-03-04T17:48:57Z)
• Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation Algorithm [7.581898299650999]
  We introduce a simple yet efficient algorithm named Quantum Qubit Rotation Algorithm (QQRA) The approximate solution of the max-cut problem can be obtained with probability close to 1. We compare it with the well known quantum approximate optimization algorithm and the classical Goemans-Williamson algorithm.
  arXiv  Detail & Related papers  (2021-10-15T11:19:48Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases. We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
  arXiv  Detail & Related papers  (2021-07-03T16:07:30Z)
• 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)
• 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)

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.