TY - JOUR
T1 - On the experimental verification of quantum complexity in linear optics
AU - Carolan, Jacques
AU - Meinecke, Jasmin D. A.
AU - Shadbolt, Peter J S
AU - Russell, Nick J
AU - Ismail, Nur
AU - Wörhoff, Kerstin
AU - Rudolph, Terry
AU - Thompson, Mark G.
AU - O'Brien, Jeremy L.
AU - Matthews, Jonathan C. F.
AU - Laing, Anthony
N1 - Comments welcome
PY - 2014/8
Y1 - 2014/8
N2 - Quantum computers promise to solve certain problems that are forever intractable to classical computers. The first of these devices are likely to tackle bespoke problems suited to their own particular physical capabilities. Sampling the probability distribution from many bosons interfering quantum-mechanically is conjectured to be intractable to a classical computer but solvable with photons in linear optics. However, the complexity of this type of problem means its solution is mathematically unverifiable, so the task of establishing successful operation becomes one of gathering sufficiently convincing circumstantial or experimental evidence. Here, we develop scalable methods to experimentally establish correct operation for this class of computation, which we implement for three, four and five photons in integrated optical circuits, on Hilbert spaces of up to 50,000 dimensions. Our broad approach is practical for all quantum computational architectures where formal verification methods for quantum algorithms are either intractable or unknown.
AB - Quantum computers promise to solve certain problems that are forever intractable to classical computers. The first of these devices are likely to tackle bespoke problems suited to their own particular physical capabilities. Sampling the probability distribution from many bosons interfering quantum-mechanically is conjectured to be intractable to a classical computer but solvable with photons in linear optics. However, the complexity of this type of problem means its solution is mathematically unverifiable, so the task of establishing successful operation becomes one of gathering sufficiently convincing circumstantial or experimental evidence. Here, we develop scalable methods to experimentally establish correct operation for this class of computation, which we implement for three, four and five photons in integrated optical circuits, on Hilbert spaces of up to 50,000 dimensions. Our broad approach is practical for all quantum computational architectures where formal verification methods for quantum algorithms are either intractable or unknown.
KW - PHOTONS
KW - INTERFERENCE
U2 - 10.1038/NPHOTON.2014.152
DO - 10.1038/NPHOTON.2014.152
M3 - Article
VL - 8
SP - 621
EP - 626
JO - Nature Photonics
JF - Nature Photonics
SN - 1749-4885
IS - 8
ER -