Decoded Quantum Interferometry Under Noise

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.

37 pages, 3 figures

References in corpus (33)

• Quantum Computing in the NISQ era and beyond
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• Adiabatic Quantum Computing
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum optimization using variational algorithms on near-term quantum devices
• Training variational quantum algorithms is NP-hard
• Barren Plateaus in Variational Quantum Computing
• Challenges and Opportunities in Quantum Optimization
• Reachability Deficits in Quantum Approximate Optimization
• Robust shadow estimation
• Noisy intermediate-scale quantum computers
• Efficient estimation of Pauli channels
• Classical Shadows With Noise
• Does provable absence of barren plateaus imply classical simulability?
• Quantum advantages for Pauli channel estimation
• Characterizing local noise in QAOA circuits
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Quantum Entropy and Central Limit Theorem
• Classical shadows with Pauli-invariant unitary ensembles
• Beyond NISQ: The Megaquop Machine
• QAOA Performance in Noisy Devices: The Effect of Classical Optimizers and Ansatz Depth
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Error-mitigated fermionic classical shadows on noisy quantum devices
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Opening the Black Box Inside Grover's Algorithm
• Multi-Angle QAOA Does Not Always Need All Its Angles
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Optimization by Decoded Quantum Interferometry
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Trainability Barriers in Low-Depth QAOA Landscapes
• Quantum Ruzsa Divergence to Quantify Magic
• Quantum Circuit Design for Decoded Quantum Interferometry