Sampling-based Quantum Optimization Algorithm with Quantum Relaxation

• URL: http://arxiv.org/abs/2504.12629v1
• Date: Thu, 17 Apr 2025 04:13:51 GMT
• Title: Sampling-based Quantum Optimization Algorithm with Quantum Relaxation
• Authors: Hiromichi Matsuyama, Yu Yamashiro,
• Abstract summary: Variational Quantum Algorithm (VQA) is a hybrid algorithm for noisy quantum devices.<n> Sampling-based Quantum Algorithms have recently been successfully applied to large-scale quantum chemistry problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variational Quantum Algorithm (VQA) is a hybrid algorithm for noisy quantum devices. However, statistical fluctuations and physical noise degrade the solution quality, so it is difficult to maintain applicability for large-scale problems. In contrast, Sampling-based Quantum Algorithms have recently been successfully applied to large-scale quantum chemistry problems. The quantum device is used only for sampling, and the ground state and its energy are estimated on the classical device. In this study, we propose the Sampling-based Quantum Optimization Algorithm (SQOA). Two challenges exist in constructing a Sampling-based Quantum Algorithm for combinatorial optimization. The first challenge is that we need to encode the optimization problem in a non-diagonal Hamiltonian, even though many VQAs encode it into the Ising Hamiltonian, which is diagonal. The second challenge is that we need a method to prepare the input state to be sampled efficiently. We employ the Quantum Relaxation (QR) method for the first challenge, which encodes multiple classical variables in one qubit. It reduces required qubits compared to the Ising Hamiltonian approach. Moreover, we investigate the parameter transferability in the Quantum Alternating Operator Ansatz for QR Hamiltonians for the second challenge. We show that restricting parameters to a linear form exhibits moderate transferability for 3-regular MaxCut problems, similar to transferability observed in the Quantum Approximate Optimization Algorithm. This property allows us to efficiently prepare the input state for a large instance using the parameters from a small instance. We leveraged transferability to create input states and applied SQOA with QR to the MaxCut instances. Transferring parameters from a 20-node problem demonstrates that SQOA with QR provides high-quality solutions for 40-node problems without variational parameter optimization.

Related papers

• Quantum Computing for Optimizing Aircraft Loading [1.055551340663609]
  The aircraft loading optimization problem is a computationally hard problem with the best known classical algorithm scaling exponentially with the number of objects.<n>We propose a quantum approach based on a multi-angle variant of the QAOA algorithm (MAL-VQA) designed to utilize a smaller number of two qubit gates in the quantum circuit.<n>We demonstrate the performance of the algorithm on different instances of the aircraft loading problem by execution on IonQ QPUs Aria and Forte.
  arXiv  Detail & Related papers  (2025-04-02T10:10:11Z)
• Non-native Quantum Generative Optimization with Adversarial Autoencoders [34.82692226532414]
  We introduce the adversarial quantum autoencoder model (AQAM) that can be used to map large-scale optimization problems onto existing quantum samplers. We demonstrate that the AQAM achieves a lower Renyi divergence and a larger spectral gap when compared to classical Markov Chain Monte Carlo samplers.
  arXiv  Detail & Related papers  (2024-07-18T18:03:18Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
  We introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization problem. We demonstrate practical viability of our method by comparing the performance of purely classical algorithms with the D-Wave Advantage 4.1 quantum annealer.
  arXiv  Detail & Related papers  (2024-04-26T21:29:42Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum-Hybrid Stereo Matching With Nonlinear Regularization and Spatial Pyramids [24.52691002678303]
  We present a new formulation for stereo matching with nonlinear regularizers and pyramids on quantum annealers.<n>Our approach is hybrid (i.e., quantum-classical) and is compatible with modern D-Wave quantum annealers.<n>We achieve an improved root mean squared accuracy over the previous state of the art in quantum stereo matching of 2% and 22.5% when using different solvers.
  arXiv  Detail & Related papers  (2023-12-26T16:53:21Z)
• Pre-optimizing variational quantum eigensolvers with tensor networks [1.4512477254432858]
  We present and benchmark an approach where we find good starting parameters for parameterized quantum circuits by simulating VQE. We apply this approach to the 1D and 2D Fermi-Hubbard model with system sizes that use up to 32 qubits. In 2D, the parameters that VTNE finds have significantly lower energy than their starting configurations, and we show that starting VQE from these parameters requires non-trivially fewer operations to come down to a given energy.
  arXiv  Detail & Related papers  (2023-10-19T17:57:58Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• Trainable Variational Quantum-Multiblock ADMM Algorithm for Generation Scheduling [0.0]
  This paper proposes a two-loop quantum solution algorithm for generation scheduling by quantum computing, machine learning, and distributed optimization. The aim is to facilitate noisy employing near-term quantum machines with a limited number of qubits to solve practical power system problems.
  arXiv  Detail & Related papers  (2023-03-28T21:31:39Z)
• 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)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)

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.