Abstract:
While universal quantum computers ideally solve problems such as factoring integers exponentially more efficiently than classical machines, the formidable challenges in building such devices motivate the demonstration of simpler, problem-specific algorithms that still promise a quantum speedup. We construct a quantum boson sampling machine (QBSM) to sample the output distribution resulting from the nonclassical interference of photons in an integrated photonic circuit, a problem thought to be exponentially hard to solve classically. Unlike universal quantum computation, boson sampling merely requires indistinguishable photons, linear state evolution, and detectors. We benchmark our QBSM with three and four photons and analyze sources of sampling inaccuracy. Our studies pave the way to larger devices that could offer the first definitive quantum-enhanced computation.

Abstract:
A boson sampling device is a specialised quantum computer that solves a problem which is strongly believed to be computationally hard for classical computers. Recently a number of small-scale implementations have been reported, all based on multi-photon interference in multimode interferometers. In the hard-to-simulate regime, even validating the device's functioning may pose a problem . In a recent paper, Gogolin et al. showed that so-called symmetric algorithms would be unable to distinguish the experimental distribution from the trivial, uniform distribution. Here we report new boson sampling experiments on larger photonic chips, and analyse the data using a scalable statistical test recently proposed by Aaronson and Arkhipov. We show the test successfully validates small experimental data samples against the hypothesis that they are uniformly distributed. We also show how to discriminate data arising from either indistinguishable or distinguishable photons. Our results pave the way towards larger boson sampling experiments whose functioning, despite being non-trivial to simulate, can be certified against alternative hypotheses.

Abstract:
It is found that $N$ identical bosons (fermions) show generalized bunching (antibunching) in $1\le \K\le M-1$ output modes of a random $M$-mode linear network: The maximum (minimum) probability of detecting all input particles in $\K$ output modes is attained only when the bosons (fermions) are completely indistinguishable. For fermions $\K$ is arbitrary, for bosons it is either ($i$) arbitrary for only classically correlated particles or ($ii$) satisfies $\K\ge N$ (or $\K=1$) for arbitrary input states. The generalized bunching supplies an efficient assessment protocol of Boson Sampling with an \textit{arbitrary network}, which requires only a polynomial number of runs of experimental device and computation of only one matrix permanent of a positive definite Hermitian matrix (with a value close to 1), with an analytic formula for the Scattershot version of Boson Sampling.

Abstract:
In this work we proof that boson sampling with $N$ particles in $M$ modes is equivalent to short-time evolution with $N$ excitations in an XY model of $2N$ spins. This mapping is efficient whenever the boson bunching probability is small, and errors can be efficiently postselected. This mapping opens the door to boson sampling with quantum simulators or general purpose quantum computers, and highlights the complexity of time-evolution with critical spin models, even for very short times.

Abstract:
We study the dynamics of photonic quantum circuits consisting of nodes coupled by quantum channels. We are interested in the regime where time delay in communication between the nodes is significant. This includes the problem of quantum feedback, where a quantum signal is fed back on a system with a time delay. We develop a matrix product state approach to solve the Quantum Stochastic Schr\"odinger Equation with time delays, which accounts in an efficient way for the entanglement of nodes with the stream of emitted photons in the waveguide, and thus the non-Markovian character of the dynamics. We illustrate this approach with two paradigmatic quantum optical examples: two coherently driven distant atoms coupled to a photonic waveguide with a time delay, and a driven atom coupled to its own output field with a time delay as an instance of a quantum feedback problem.

Abstract:
We consider boolean circuits computing n-operators f:{0,1}^n --> {0,1}^n. As gates we allow arbitrary boolean functions; neither fanin nor fanout of gates is restricted. An operator is linear if it computes n linear forms, that is, computes a matrix-vector product y=Ax over GF(2). We prove the existence of n-operators requiring about n^2 wires in any circuit, and linear n-operators requiring about n^2/\log n wires in depth-2 circuits, if either all output gates or all gates on the middle layer are linear.

Abstract:
We demonstrate photonic quantum circuits that operate at the stringent levels that will be required for future quantum information science and technology. These circuits are fabricated from silica-on-silicon waveguides forming directional couplers and interferometers. While our focus is on the operation of quantum circuits, to test this operation required construction of a spectrally tuned photon source to produce near-identical pairs of photons. We show non-classical interference with two photons and a two-photon entangling logic gate that operate with near-unit fidelity. These results are a significant step towards large-scale operation of photonic quantum circuits.

Abstract:
We suggest a novel conceptual approach for describing the properties of waveguides and circuits in photonic crystals, based on the effective discrete equations that include the long-range interaction effects. We demonstrate, on the example of sharp waveguide bends, that our approach is very effective and accurate for the study of bound states and transmission spectra of the photonic-crystal circuits, and disclose the importance of evanescent modes in their properties.

Abstract:
We report photonic quantum circuits created using an ultrafast laser processing technique that is rapid, requires no lithographic mask and can be used to create three-dimensional networks of waveguide devices. We have characterized directional couplers--the key functional elements of photonic quantum circuits--and found that they perform as well as lithographically produced waveguide devices. We further demonstrate high-performance interferometers and an important multi-photon quantum interference phenomenon for the first time in integrated optics. This direct-write approach will enable the rapid development of sophisticated quantum optical circuits and their scaling into three-dimensions.

Abstract:
Quantum computers are expected to be more efficient in performing certain computations than any classical machine. Unfortunately, the technological challenges associated with building a full-scale quantum computer have not yet allowed the experimental verification of such an expectation. Recently, boson sampling has emerged as a problem that is suspected to be intractable on any classical computer, but efficiently implementable with a linear quantum optical setup. Therefore, boson sampling may offer an experimentally realizable challenge to the Extended Church-Turing thesis and this remarkable possibility motivated much of the interest around boson sampling, at least in relation to complexity-theoretic questions. In this work, we show that the successful development of a boson sampling apparatus would not only answer such inquiries, but also yield a practical tool for difficult molecular computations. Specifically, we show that a boson sampling device with a modified input state can be used to generate molecular vibronic spectra, including complicated effects such as Duschinsky rotations.