Decoded Quantum Interferometry Under Noise

• URL: http://arxiv.org/abs/2508.10725v1
• Date: Thu, 14 Aug 2025 15:08:09 GMT
• Title: Decoded Quantum Interferometry Under Noise
• Authors: Kaifeng Bu, Weichen Gu, Dax Enshan Koh, Xiang Li,
• Abstract summary: We present a rigorous analysis of Decoded Quantum Interferometry (DQI) under noise.<n>For the maximum linear satisfiability problem, we prove that, in the presence of noise, performance is governed by a noise-weighted sparsity parameter of the instance matrix.<n>We offer guidance on preserving DQI's potential quantum advantage under realistic noise.
• Score: 4.180458188910334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decoded Quantum Interferometry (DQI) is a recently proposed quantum optimization algorithm that exploits sparsity in the Fourier spectrum of objective functions, with the potential for exponential speedups over classical algorithms on suitably structured problems. While highly promising in idealized settings, its resilience to noise has until now been largely unexplored. To address this, we conduct a rigorous analysis of DQI under noise, focusing on local depolarizing noise. For the maximum linear satisfiability problem, we prove that, in the presence of noise, performance is governed by a noise-weighted sparsity parameter of the instance matrix, with solution quality decaying exponentially as sparsity decreases. We demonstrate this decay through numerical simulations on two special cases: the Optimal Polynomial Intersection problem and the Maximum XOR Satisfiability problem. The Fourier-analytic methods we develop can be readily adapted to other classes of random Pauli noise, making our framework applicable to a broad range of noisy quantum settings and offering guidance on preserving DQI's potential quantum advantage under realistic noise.

Related papers

• Design and Analysis of an Improved Constrained Hypercube Mixer in Quantum Approximate Optimization Algorithm [0.0]
  In the Noisy Intermediate-Scale Quantum (NISQ) era, QAOA is not suited for constrained problems.<n>One way to incorporate certain types of constraints is to restrict the mixing operator to the feasible subspace.<n>We present a modification that generates circuits with fewer gates for a broad class of constrained problems.
  arXiv  Detail & Related papers  (2026-03-05T13:57:15Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• Variational noise mitigation in quantum circuits: the case of Quantum Fourier Transform [35.18016233072556]
  We perform numerical simulations for two qubits under both coherent and incoherent noise.<n>Our results show that the variational circuit can reproduce the QFT with higher fidelity in scenarios dominated by coherent noise.<n>This demonstrates the potential of the approach as an effective error-mitigation strategy for small- to medium-scale quantum systems.
  arXiv  Detail & Related papers  (2025-11-07T14:35:55Z)
• Benchmarking Quantum Solvers in Noisy Digital Simulations for Financial Portfolio Optimization [6.856553510045862]
  We benchmark two prominent quantum algorithms: Quantum Imaginary-Time Evolution (QITE) and the Quantum Approximate Optimization Algorithm (QAOA)<n>We apply them to the Markowitz portfolio optimization problem in quantitative finance, on both digital quantum computers and local quantum simulators with controllable two-qubit errors (noise)<n>Our findings provide valuable insights into the trade-offs between scalability and noise tolerance and demonstrate the practical potential of quantum algorithms for solving real-world optimization problems on near-term quantum devices.
  arXiv  Detail & Related papers  (2025-08-28T18:00:08Z)
• RhoDARTS: Differentiable Quantum Architecture Search with Density Matrix Simulations [44.13836547616739]
  Variational Quantum Algorithms (VQAs) are a promising approach to leverage Noisy Intermediate-Scale Quantum (NISQ) computers.<n> choosing optimal quantum circuits that efficiently solve a given VQA problem is a non-trivial task.<n>Quantum Architecture Search (QAS) algorithms enable automatic generation of quantum circuits tailored to the provided problem.
  arXiv  Detail & Related papers  (2025-06-04T08:30:35Z)
• Provably Robust Training of Quantum Circuit Classifiers Against Parameter Noise [49.97673761305336]
  Noise remains a major obstacle to achieving reliable quantum algorithms.<n>We present a provably noise-resilient training theory and algorithm to enhance the robustness of parameterized quantum circuit classifiers.
  arXiv  Detail & Related papers  (2025-05-24T02:51:34Z)
• Non-Markovian Noise Mitigation: Practical Implementation, Error Analysis, and the Role of Environment Spectral Properties [3.1003326924534482]
  We propose a non-Markovian Noise Mitigation(NMNM) method by extending the probabilistic error cancellation (PEC) method in the QEM framework to treat non-Markovian noise.<n>We establish a direct connection between the overall approximation error and sampling overhead of QEM and the spectral property of the environment.
  arXiv  Detail & Related papers  (2025-01-09T07:22:06Z)
• Bayesian Quantum Amplitude Estimation [49.1574468325115]
  We present BAE, a problem-tailored and noise-aware Bayesian algorithm for quantum amplitude estimation.<n>In a fault tolerant scenario, BAE is capable of saturating the Heisenberg limit; if device noise is present, BAE can dynamically characterize it and self-adapt.<n>We propose a benchmark for amplitude estimation algorithms and use it to test BAE against other approaches.
  arXiv  Detail & Related papers  (2024-12-05T18:09:41Z)
• Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation [0.0]
  We present a hybrid quantum algorithm for estimating gaps in many-body energy spectra.<n>We employ error mitigation strategies that optimize the utilization of quantum resources.<n>Results underscore the potential to enable accurate quantum simulations on near-term noisy quantum devices.
  arXiv  Detail & Related papers  (2024-05-16T17:57:15Z)
• Lindblad-like quantum tomography for non-Markovian quantum dynamical maps [46.350147604946095]
  We introduce Lindblad-like quantum tomography (L$ell$QT) as a quantum characterization technique of time-correlated noise in quantum information processors.<n>We discuss L$ell$QT for the dephasing dynamics of single qubits in detail, which allows for a neat understanding of the importance of including multiple snapshots of the quantum evolution in the likelihood function.
  arXiv  Detail & Related papers  (2024-03-28T19:29:12Z)
• Compressed-sensing Lindbladian quantum tomography with trapped ions [44.99833362998488]
  Characterizing the dynamics of quantum systems is a central task for the development of quantum information processors. We propose two different improvements of Lindbladian quantum tomography (LQT) that alleviate previous shortcomings.
  arXiv  Detail & Related papers  (2024-03-12T09:58:37Z)
• Emergence of noise-induced barren plateaus in arbitrary layered noise models [44.99833362998488]
  In variational quantum algorithms the parameters of a parameterized quantum circuit are optimized in order to minimize a cost function that encodes the solution of the problem. We discuss how, and in which sense, the phenomenon of noise-induced barren plateaus emerges in parameterized quantum circuits with a layered noise model.
  arXiv  Detail & Related papers  (2023-10-12T15:18:27Z)
• Distributionally Robust Variational Quantum Algorithms with Shifted Noise [9.705847892362165]
  We show how to optimize variational quantum algorithms (VQAs) to be robust against unknown shifted noise. This work is the first step towards improving the reliability of VQAs influenced by shifted noise.
  arXiv  Detail & Related papers  (2023-08-28T23:19:57Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Policy Gradient based Quantum Approximate Optimization Algorithm [2.5614220901453333]
  We show that policy-gradient-based reinforcement learning algorithms are well suited for optimizing the variational parameters of QAOA in a noise-robust fashion. We analyze the performance of the algorithm for quantum state transfer problems in single- and multi-qubit systems.
  arXiv  Detail & Related papers  (2020-02-04T00:46: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.