Song, Wooyeong Lim, Youngrong Jeong, Kabgyun Ji, Yun-Seong Lee, Jinhyoung Kim, Jaewan Kim, M. S. Bang, Jeongho 2024-01-19T12:30:31Z 2024-01-19T12:30:31Z 2022-04-05 2022-04 2058-9565 https://pubs.kist.re.kr/handle/201004/115477 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 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 Ax approximate to b + eta, where 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. English IOP PUBLISHING LTD Quantum solvability of noisy linear problems by divide-and-conquer strategy Article 10.1088/2058-9565/ac51b0 1 Quantum Science and Technology, v.7, no.2 Quantum Science and Technology 7 2 N scie scopus 000766354800001 Quantum Science & Technology Physics, Multidisciplinary Physics Article COMPLEXITY SUPREMACY quantum algorithm noisy linear problem quantum-sample complexity