Quantum solvability of noisy linear problems by divide-and-conquer strategy
File(s)submit_qnlp_ver17.0.pdf (643.02 KB)
Accepted version
Author(s)
Type
Journal Article
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 b constructed using a finite set of samples, a hidden vector or structure involved in b is obtained by solving a noise-corrupted linear equation $\hat{A}\mathbf{x}\approx \mathbf{b}+\boldsymbol{\eta }$, where η 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.
Date Issued
2022-04-01
Date Acceptance
2022-02-03
Citation
Quantum Science and Technology, 2022, 7 (2)
ISSN
2058-9565
Publisher
IOP Publishing
Journal / Book Title
Quantum Science and Technology
Volume
7
Issue
2
Copyright Statement
© 2022 IOP Publishing Ltd. This is an author-created, un-copyedited version of an article accepted for publication in Quantum Science and Technology. IOP Publishing Ltd is not responsible for any errors or omissions in this version of the manuscript or any version derived from it. The definitive publisher authenticated version is available online at 10.1088/2058-9565/ac51b0
Sponsor
Engineering & Physical Science Research Council (E
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000766354800001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Grant Number
EP/T001062/1
Subjects
Science & Technology
Physical Sciences
Quantum Science & Technology
Physics, Multidisciplinary
Physics
quantum algorithm
noisy linear problem
quantum-sample complexity
COMPLEXITY
SUPREMACY
Publication Status
Published online
Article Number
ARTN 025009
Date Publish Online
2022-03-01