상세정보
학술지
Quantum Solvability of Noisy Linear Problems by Divide-and-conquer Strategy
- 저자
- 송우영, 임영롱, 정갑균, 지윤성, 이진형, 김재완, 김명식, 방정호
- 발행일
- 202204
- 출처
- Quantum Science and Technology, v.7 no.2, pp.1-8
- ISSN
- 2058-9565
- 출판사
- Institute of Physics (IOP)
- 협약과제
- 21JB3900, 양자데이터 최적화 중심 양자 알고리즘 개발 및 활용 연구, 방정호
- 초록
- 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+η, 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.
- KSP 제안 키워드
- Divide-and-conquer, Engineering disciplines, Large core, Linear equations, Noise Model, Reduced form, linear problem, quantum algorithm, quantum computer