In this section
@article{Song:2022:2058-9565/ac51b0,
author = {Song, W and Lim, Y and Jeong, K and Ji, Y-S and Lee, J and Kim, J and Kim, MS and Bang, J},
doi = {2058-9565/ac51b0},
journal = {Quantum Science and Technology},
title = {Quantum solvability of noisy linear problems by divide-and-conquer strategy},
url = {http://dx.doi.org/10.1088/2058-9565/ac51b0},
volume = {7},
year = {2022}
}
TY - JOUR
AB - 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.
AU - Song,W
AU - Lim,Y
AU - Jeong,K
AU - Ji,Y-S
AU - Lee,J
AU - Kim,J
AU - Kim,MS
AU - Bang,J
DO - 2058-9565/ac51b0
PY - 2022///
SN - 2058-9565
TI - Quantum solvability of noisy linear problems by divide-and-conquer strategy
T2 - Quantum Science and Technology
UR - http://dx.doi.org/10.1088/2058-9565/ac51b0
UR - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000766354800001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR - https://iopscience.iop.org/article/10.1088/2058-9565/ac51b0
UR - http://hdl.handle.net/10044/1/96021
VL - 7
ER -