What can quantum optics say about computational complexity theory?

Rahimi-Keshari, Saleh, Lund, Austin P and Ralph, Timothy C (2015) What can quantum optics say about computational complexity theory?. Physical Review Letters, 114 6: . doi:10.1103/PhysRevLett.114.060501

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
UQ352832_OA.pdf Full text (open access) application/pdf 154.62KB 0

Author Rahimi-Keshari, Saleh
Lund, Austin P
Ralph, Timothy C
Title What can quantum optics say about computational complexity theory?
Journal name Physical Review Letters   Check publisher's open access policy
ISSN 1079-7114
Publication date 2015-02-11
Year available 2015
Sub-type Article (original research)
DOI 10.1103/PhysRevLett.114.060501
Open Access Status File (Publisher version)
Volume 114
Issue 6
Total pages 5
Place of publication College Park, United States
Publisher American Physical Society
Language eng
Formatted abstract
Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain results that are of interest from both quantum theory and the computational complexity theory point of view. We derive a general formula for calculating the output probabilities, and by considering input thermal states, we show that the output probabilities are proportional to permanents of positive-semidefinite Hermitian matrices. It is believed that approximating permanents of complex matrices in general is a #P-hard problem. However, we show that these permanents can be approximated with an algorithm in the BPPNP complexity class, as there exists an efficient classical algorithm for sampling from the output probability distribution. We further consider input squeezed-vacuum states and discuss the complexity of sampling from the probability distribution at the output.
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Centre for Quantum Computer Technology Publications
Official 2016 Collection
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 10 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 9 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 03 Mar 2015, 10:26:21 EST by System User on behalf of Scholarly Communication and Digitisation Service