Imperial College London
Portrait Picture

Professor Myungshik Kim

Faculty of Natural Sciences, Department of Physics

Chair in Theoretical Quantum Information Sciences
 
 
 
//

Contact

 

+44 (0)20 7594 7754m.kim

 
 
//

Location

 

1202Electrical EngineeringSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@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}
}
Download

RIS format (EndNote, RefMan)

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  -
Download