The Role of Entanglement in Quantum-Relaxation Based Optimization Algorithms

• URL: http://arxiv.org/abs/2302.00429v2
• Date: Sun, 9 Apr 2023 09:08:20 GMT
• Title: The Role of Entanglement in Quantum-Relaxation Based Optimization Algorithms
• Authors: Kosei Teramoto and Rudy Raymond and Hiroshi Imai
• Abstract summary: Quantum Random Access Code (QRAC) encodes multiple variables of binary optimization in a single qubit. Our results suggest that QRAO not only can scale solvable instances of binary optimization problems with limited quantum computers but also can benefit from quantum entanglement.
• Score: 4.00916638804083
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Random Access Optimizer (QRAO) is a quantum-relaxation based optimization algorithm proposed by Fuller et al. that utilizes Quantum Random Access Code (QRAC) to encode multiple variables of binary optimization in a single qubit. Differing from standard quantum optimizers such as QAOA, it utilizes the eigenstates of local quantum Hamiltonians that are not diagonal in the computational basis. There are indications that quantum entanglement may not be needed to solve binary optimization problems with standard quantum optimizers because their maximal eigenstates of diagonal Hamiltonians include classical states. In this study, while quantumness does not always improve the performance of quantum relaxations, we observed that there exist some instances in which quantum relaxation succeeds to find optimal solutions with the help of quantumness. Our results suggest that QRAO not only can scale the instances of binary optimization problems solvable with limited quantum computers but also can benefit from quantum entanglement.

Related papers

• Combinatorial Optimization with Quantum Computers [1.199955563466263]
  Quantum computers do computation with a potential advantage over classical computers. A quantum computer can apply the operator to a superposition of binary strings to provide a superposition of binary outputs. A family of quantum machines called quantum annealers are specially designed to solve optimization problems.
  arXiv  Detail & Related papers  (2024-12-20T10:46:18Z)
• Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing [0.0]
  We demonstrate in this work how quantums with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems. A key feature of our algorithm is it not only from the best solution returned by the quantum but from all solutions below a certain cost threshold.
  arXiv  Detail & Related papers  (2024-12-20T08:27:23Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
  We introduce an iterative quantum optimization algorithm to solve optimization problems. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement.
  arXiv  Detail & Related papers  (2023-03-09T18:59:37Z)
• 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)
• Variational Quantum Non-Orthogonal Optimization [0.0]
  We show that it is possible to significantly reduce the number of qubits required to solve complex optimization problems. Our proposal opens the path towards solving real-life useful optimization problems in today's limited quantum hardware.
  arXiv  Detail & Related papers  (2022-10-06T18:00:02Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• 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)
• 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 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)

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.