Quantum solvability of noisy linear problems by divide-and-conquer strategy

Abstract

Noisy linear problems have been studied in various science and engineering disciplines. A class of "hard" noisy linear problems can be formulated as follows: Given a matrix $\hat{A}$ and a vector $\mathbf{b}$ constructed using a finite set of samples, a hidden vector or structure involved in $\mathbf{b}$ is obtained by solving a noise-corrupted linear equation $\hat{A}\mathbf{x}\approx \mathbf{b}+\mathbf{\eta }$, where $\mathbf{\eta }$ is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.

arXiv commentpublished version

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum random access memory
• Architectures for a quantum random access memory
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Quantum learning robust to noise
• Learning with Errors is easy with quantum samples
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Quantum-classical reinforcement learning for decoding noisy classical parity information

Cited by in corpus (4)

• Quantum-Classical Hybrid Algorithm for Solving the Learning-With-Errors Problem on NISQ Devices
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation
• Sample-size-reduction of quantum states for the noisy linear problem
• Assessing the feasibility of quantum learning algorithms for noisy linear problems