Quantum sampling problems, BosonSampling and quantum supremacy

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 p...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	A. P. Lund, Michael J. Bremner, T. C. Ralph
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2017
Materias:	Physics QC1-999 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/626c8c545e0c4c84a3aad0be80c3b336
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:626c8c545e0c4c84a3aad0be80c3b336
record_format	dspace
spelling	oai:doaj.org-article:626c8c545e0c4c84a3aad0be80c3b3362021-12-02T16:09:13ZQuantum sampling problems, BosonSampling and quantum supremacy10.1038/s41534-017-0018-22056-6387https://doaj.org/article/626c8c545e0c4c84a3aad0be80c3b3362017-04-01T00:00:00Zhttps://doi.org/10.1038/s41534-017-0018-2https://doaj.org/toc/2056-6387Abstract 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.A. P. LundMichael J. BremnerT. C. RalphNature PortfolioarticlePhysicsQC1-999Electronic computers. Computer scienceQA75.5-76.95ENnpj Quantum Information, Vol 3, Iss 1, Pp 1-8 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	Physics QC1-999 Electronic computers. Computer science QA75.5-76.95
spellingShingle	Physics QC1-999 Electronic computers. Computer science QA75.5-76.95 A. P. Lund Michael J. Bremner T. C. Ralph Quantum sampling problems, BosonSampling and quantum supremacy
description	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.
format	article
author	A. P. Lund Michael J. Bremner T. C. Ralph
author_facet	A. P. Lund Michael J. Bremner T. C. Ralph
author_sort	A. P. Lund
title	Quantum sampling problems, BosonSampling and quantum supremacy
title_short	Quantum sampling problems, BosonSampling and quantum supremacy
title_full	Quantum sampling problems, BosonSampling and quantum supremacy
title_fullStr	Quantum sampling problems, BosonSampling and quantum supremacy
title_full_unstemmed	Quantum sampling problems, BosonSampling and quantum supremacy
title_sort	quantum sampling problems, bosonsampling and quantum supremacy
publisher	Nature Portfolio
publishDate	2017
url	https://doaj.org/article/626c8c545e0c4c84a3aad0be80c3b336
work_keys_str_mv	AT aplund quantumsamplingproblemsbosonsamplingandquantumsupremacy AT michaeljbremner quantumsamplingproblemsbosonsamplingandquantumsupremacy AT tcralph quantumsamplingproblemsbosonsamplingandquantumsupremacy
_version_	1718384472631541760

Quantum sampling problems, BosonSampling and quantum supremacy

Ejemplares similares