2019/08/31 by Wooyeong Song, Youngrong Lim, Kabgyun Jeong +5 · 5 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Applied mathematics #Complexity and Algorithms in Graphs #Computer science #Cryptography and Data Security #Divide and conquer algorithms #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum mechanics #Statistical physics #quant-ph
paper · pdf · open access · doi:10.1088/2058-9565/ac51b0
published in Quantum Science and Technology 7(2), 025009 (IOP Publishing) · published version
openalex publication_date 2022/02/03 · arxiv created 2022/03/11 · arxiv updated 2022/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 ≈ b + \boldsymbolη, where \boldsymbolη 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.