Quantum sampling problems, BosonSampling and quantum supremacy

Lund, A. P., Bremner, Michael J. and Ralph, T. C. (2017) Quantum sampling problems, BosonSampling and quantum supremacy. NPJ Quantum Information, 3 1: . doi:10.1038/s41534-017-0018-2

Author Lund, A. P.
Bremner, Michael J.
Ralph, T. C.
Title Quantum sampling problems, BosonSampling and quantum supremacy
Journal name NPJ Quantum Information   Check publisher's open access policy
ISSN 2056-6387
Publication date 2017-04-13
Year available 2017
Sub-type Critical review of research, literature review, critical commentary
DOI 10.1038/s41534-017-0018-2
Open Access Status DOI
Volume 3
Issue 1
Total pages 8
Place of publication London, United Kingdom
Publisher Nature Publishing Group
Language eng
Subject 1701 Computer Science (miscellaneous)
1703 Computational Theory and Mathematics
1705 Computer Networks and Communications
3109 Statistical and Nonlinear Physics
Abstract There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.
Keyword Physics, Applied
Physics, Atomic, Molecular & Chemical
Physics, Condensed Matter
Q-Index Code C1
Q-Index Status Provisional Code
Grant ID CE110001027
Institutional Status UQ

Document type: Journal Article
Sub-type: Critical review of research, literature review, critical commentary
Collections: School of Mathematics and Physics
HERDC Pre-Audit
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 7 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 5 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Mon, 15 May 2017, 01:00:42 EST by Web Cron on behalf of Learning and Research Services (UQ Library)