Noise Robustness of Quantum Relaxation for Combinatorial Optimization

• URL: http://arxiv.org/abs/2403.05153v1
• Date: Fri, 8 Mar 2024 08:41:55 GMT
• Title: Noise Robustness of Quantum Relaxation for Combinatorial Optimization
• Authors: Kentaro Tamura, Yohichi Suzuki, Rudy Raymond, Hiroshi C. Watanabe, Yuki Sato, Ruho Kondo, Michihiko Sugawara, Naoki Yamamoto
• Abstract summary: QRAO is a relaxation algorithm that reduces the number of qubits required to solve a problem. Noise affects the quality of the binary solution of QRAO, which is unknown. We discuss a plausible mechanism behind the robustness of QRAO under depolarizing noise.
• Score: 2.768724463950609
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: QRAO (Quantum Random Access Optimization) is a relaxation algorithm that reduces the number of qubits required to solve a problem by encoding multiple variables per qubit using QRAC (Quantum Random Access Code). Reducing the number of qubits is a common way of dealing with the impact of noise on a quantum algorithm. Our interest lies in the impact of noise on the quality of the binary solution of QRAO, which is unknown. We demonstrate that the mean approximation ratio of the (3, 1)-QRAC Hamiltonian, i.e., the Hamiltonian utilizing the encoding of 3 bits into 1 qubit by QRAC, is less affected by noise compared to the Ising Hamiltonian used in quantum annealer and QAOA (Quantum Approximate Optimization Algorithm). Based on this observation, we discuss a plausible mechanism behind the robustness of QRAO under depolarizing noise. Finally, we assess the number of shots required to estimate the values of binary variables correctly under depolarizing noise and show that the (3, 1)-QRAC Hamiltonian requires less shots to achieve the same accuracy compared to the Ising Hamiltonian.

Related papers

• Sampling-based Quantum Optimization Algorithm with Quantum Relaxation [0.0]
  Variational Quantum Algorithm (VQA) is a hybrid algorithm for noisy quantum devices. Sampling-based Quantum Algorithms have recently been successfully applied to large-scale quantum chemistry problems.
  arXiv  Detail & Related papers  (2025-04-17T04:13:51Z)
• Q-Cluster: Quantum Error Mitigation Through Noise-Aware Unsupervised Learning [4.984018914962973]
  Quantum error mitigation (QEM) is critical in reducing the impact of noise in quantum computing. We propose a novel QEM approach, Q-Cluster, that uses unsupervised learning (clustering) to reshape the measured bit-string distribution. We show that our proposed Q-Cluster scheme improves the fidelity by a factor of 1.46x, on average, compared to the unmitigated output distribution.
  arXiv  Detail & Related papers  (2025-04-15T01:53:39Z)
• ParetoQ: Scaling Laws in Extremely Low-bit LLM Quantization [58.84018707089315]
  We present a unified framework for rigorous comparisons across 1-bit, 1.58-bit, 2-bit, 3-bit, and 4-bit quantization settings. We show that ternary, 2-bit, and 3-bit quantization maintains comparable performance in the size-accuracy trade-off. Considering hardware constraints, 2-bit quantization offers promising potential for memory reduction and speedup.
  arXiv  Detail & Related papers  (2025-02-04T18:59:26Z)
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization [35.18016233072556]
  Combinatorial optimization plays a crucial role in many industrial applications.<n>We present an enhanced bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm to address higher-order unconstrained binary optimization (HUBO)<n>Our results show that BF-DCQO offers an effective path for solving large-scale HUBO problems on current and near-term quantum processors.
  arXiv  Detail & Related papers  (2024-09-05T17:38:59Z)
• Optimized Noise Suppression for Quantum Circuits [0.40964539027092917]
  Crosstalk noise is a severe error source in, e.g., cross-resonance based superconducting quantum processors. Intrepid programming algorithm extends previous work on optimized qubit routing by swap insertion. We evaluate the proposed method by characterizing crosstalk noise for two chips with up to 127 qubits.
  arXiv  Detail & Related papers  (2024-01-12T07:34:59Z)
• Quantum Algorithm for Signal Denoising [32.77959665599749]
  The proposed algorithm is able to process textitboth classical and quantum signals. Numerical results show that it is efficient at removing noise of both classical and quantum origin.
  arXiv  Detail & Related papers  (2023-12-24T05:16:04Z)
• Accurate and Honest Approximation of Correlated Qubit Noise [39.58317527488534]
  We propose an efficient systematic construction of approximate noise channels, where their accuracy can be enhanced by incorporating noise components with higher qubit-qubit correlation degree. We find that, for realistic noise strength typical for fixed-frequency superconducting qubits, correlated noise beyond two-qubit correlation can significantly affect the code simulation accuracy.
  arXiv  Detail & Related papers  (2023-11-15T19:00:34Z)
• Quantum Approximate Optimization Algorithm with Cat Qubits [0.0]
  We numerically simulate solving MaxCut problems using QAOA with cat qubits. We show that running QAOA with cat qubits increases the approximation ratio for random instances of MaxCut with respect to qubits encoded into two-level systems.
  arXiv  Detail & Related papers  (2023-05-09T15:44:52Z)
• 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)
• Error Mitigation-Aided Optimization of Parameterized Quantum Circuits: Convergence Analysis [42.275148861039895]
  Variational quantum algorithms (VQAs) offer the most promising path to obtaining quantum advantages via noisy processors. gate noise due to imperfections and decoherence affects the gradient estimates by introducing a bias. Quantum error mitigation (QEM) techniques can reduce the estimation bias without requiring any increase in the number of qubits. QEM can reduce the number of required iterations, but only as long as the quantum noise level is sufficiently small.
  arXiv  Detail & Related papers  (2022-09-23T10:48:04Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum error mitigation via matrix product operators [27.426057220671336]
  Quantum error mitigation (QEM) can suppress errors in measurement results via repeated experiments and post decomposition of data. MPO representation increases the accuracy of modeling noise without consuming more experimental resources. Our method is hopeful of being applied to circuits in higher dimensions with more qubits and deeper depth.
  arXiv  Detail & Related papers  (2022-01-03T16:57:43Z)
• Multistate Transition Dynamics by Strong Time-Dependent Perturbation in NISQ era [0.0]
  We develop a quantum computing scheme utilizing McLachlan variational principle in a hybrid quantum-classical algorithm. Results for transition probabilities are obtained with accuracy better than 1%, as established by comparison to the benchmark data.
  arXiv  Detail & Related papers  (2021-12-13T00:49:15Z)
• A loop Quantum Approximate Optimization Algorithm with Hamiltonian updating [0.0]
  We propose a quantum approximate optimization algorithm(QAOA) with a very shallow circuit, called loop-QAOA, to avoid issues of noises at intermediate depths. The insight of exploiting outputs from shallow circuits as bias may be applied for other quantum algorithms.
  arXiv  Detail & Related papers  (2021-09-23T12:55:51Z)
• Optimization and Noise Analysis of the Quantum Algorithm for Solving One-Dimensional Poisson Equation [17.65730040410185]
  We propose an efficient quantum algorithm for solving one-dimensional Poisson equation. We further develop this algorithm to make it closer to the real application on the noisy intermediate-scale quantum (NISQ) devices. We analyze the effect of common noise existing in the real quantum devices on our algorithm using the IBM Qiskit toolkit.
  arXiv  Detail & Related papers  (2021-08-27T09:44:41Z)
• 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)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.