Boson Sampling is a computational task strongly believed to be hard for classical computers, but efficiently solvable by orchestrated bosonic interference in specialised quantum computer. Current experimental schemes, however, are still insufficient convincing demonstration of the advantage over computation. A new variation this task, Scattershot Sampling, leads an exponential increase speed device, using larger number photon sources based on parametric downconversion. This achieved having...

Abstract The geometrical arrangement of a set quantum states can be completely characterized using relational information only. This is encoded in the pairwise state overlaps, as well Bargmann invariants higher degree written traces products density matrices. We describe how to measure suitable generalizations SWAP test. allows for complete and robust characterization projective-unitary invariant properties any pure or mixed states. As applications, we basis-independent tests linear...

A fundamental and open question is whether cross-Kerr nonlinearities can be used to construct a controlled-phase (cphase) gate. Here we propose gate constructed from discrete set of atom-mediated interaction sites with counterpropagating photons. We show that the average fidelity F between cphase our proposed increases as number spectral width photon decreases; e.g., 12 find F>99%.

We perform a comprehensive set of experiments that characterize bosonic bunching up to 3 photons in interferometers 16 modes. Our verify two rules govern bunching. The first rule, obtained recently [1,2], predicts the average behavior probability and is known as birthday paradox. second rule new, establishes n!-factor quantum enhancement for all n bosons bunch single output mode, with respect case distinguishable bosons. Besides its fundamental importance phenomena such Bose-Einstein...

We explore the possibility of efficient classical simulation linear optics experiments under effect particle losses. Specifically, we investigate canonical boson sampling scenario in which an $n$-particle Fock input state propagates through a linear-optical network and is subsequently measured by particle-number detectors $m$ output modes. examine two models In first model fixed number particles lost. prove that this statistics can be well approximated simulation, provided photons left grows...

BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected be hard for classical computers. Since these devices not universal computation, it remains open question whether any error-correction techniques can applied them, and thus important investigate how robust the under natural experimental imperfections, such as losses imperfect control parameters. Here, we complexity photon losses, more specifically, case...

As a promising candidate for exhibiting quantum computational supremacy, Gaussian boson sampling (GBS) is designed to exploit the ease of experimental preparation states. However, sufficiently large and inevitable noise might render GBS classically simulable. In this work, we formalize intuition by establishing sufficient condition approximate polynomial-time classical simulation noisy GBS-in form an inequality between input squeezing parameter, overall transmission rate, quality photon...

Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as platform for building devices capable performing tasks are out reach classical devices. There therefore significant interest, from the perspective computational complexity theory, in solidifying mathematical foundation hardness simulating these We show that, under standard Anti-Concentration and Permanent-of-Gaussians conjectures, there no efficient algorithm to sample ideal distributions (even...

The Boson sampling problem consists in from the output probability distribution of a bosonic Fock state, after it evolves through linear interferometer. There is strong evidence that computationally hard for classical computers, while can be solved naturally by bosons. This has led to draw increasing attention as possible way provide experimental quantum computational supremacy. Nevertheless, very complexity makes exclude hypothesis data are sampled different distribution. By exploiting...

A cross-Kerr interaction produces a phase shift on two modes of light proportional to the number photons in both and is sometimes called cross-phase modulation. Cross-Kerr nonlinearities have many applications classical quantum nonlinear optics, including possibility deterministic all-optical controlled-phase gate. We calculate one- two-photon $S$ matrices for fields propagating medium where spatially distributed at discrete sites comprised atoms. For interactions considered, we analyze...

Bosonic interference is a fundamental physical phenomenon, and it believed to lie at the heart of quantum computational advantage. It thus necessary develop practical tools witness its presence, both for reliable assessment source investigations. Here we describe how linear interferometers can be used unambiguously genuine n-boson indistinguishability. The amount violation proposed witnesses bounds degree multi-boson indistinguishability, which also provide novel intuitive model using set...

Matchgates are a restricted set of two-qubit gates known to be classically simulable under particular conditions. Specifically, if circuit consists only nearest-neighbour matchgates, an efficient classical simulation is possible either (i) the input computational basis state and requires computing probabilities multi-qubit outcomes (including also adaptive measurements), or (ii) arbitrary product state, but output single qubit. In this paper we extend these results show that matchgates even...

Photonic interference is a key quantum resource for optical computation, and in particular so-called boson sampling devices. In interferometers with certain symmetries, genuine multiphoton effectively suppresses sets of events, as the original Hong–Ou–Mandel effect. Recently, it was shown that some classical semi-classical models could be ruled out by identifying such suppressions Fourier interferometers. Here we propose suppression law suitable random-input experiments multimode Sylvester...

Boson Sampling is a task that conjectured to be computationally hard for classical computer, but which can efficiently solved by linear-optical interferometers with Fock state inputs. Significant advances have been reported in the last few years, demonstrations of small- and medium-scale devices, as well implementations variants such Gaussian Sampling. Besides relevance this class computational models quest unambiguous experimental quantum advantage, recent results also proposed first...

Matchgates are a family of two-qubit gates associated with noninteracting fermions. They classically simulatable if acting only on nearest neighbors, but become universal for quantum computation we relax this restriction or use SWAP [Jozsa and Miyake, Proc. R. Soc. A 464, 3089 (2008)]. We generalize result by proving that any nonmatchgate parity-preserving unitary is capable extending the computational power matchgates into computation. identify single local invariant unitaries responsible...

Photon indistinguishability plays a fundamental role in information processing, with applications such as linear-optical quantum computation and metrology. It is then necessary to develop appropriate tools quantify the amount of this resource multiparticle scenario. Here we report four-photon experiment interferometer designed simultaneously estimate degree between three pairs photons. The design dispenses need heralding for parametric down-conversion sources, resulting an efficient reliable...

Suppose we have $N$ quantum systems in unknown states $\left|{\ensuremath{\psi}}_{i}\right\ensuremath{\rangle}$, but know the value of some pairwise overlaps ${\left|\ensuremath{\langle}{\ensuremath{\psi}}_{k}|{\ensuremath{\psi}}_{l}\ensuremath{\rangle}\right|}^{2}$. What can say about values overlaps? We provide a complete answer to this problem for three pure and two given way obtain bounds general case. discuss how contrasts from that classical model featuring only coherence-free,...

Particle indistinguishability is at the heart of quantum statistics that regulates fundamental phenomena such as electronic band structure solids, Bose-Einstein condensation and superconductivity. Moreover, it necessary in practical applications linear optical computation simulation, particular for Boson Sampling devices. It thus crucial to develop tools certify genuine multiphoton interference between multiple sources. Our approach employs total variation distance find those transformations...

BosonSampling is a restricted model of quantum computation proposed recently, where non-adaptive linear-optical network used to solve sampling problem that seems be hard for classical computers. Here we show that, even if the has constant number (greater than four) beam splitter layers, exact version still classically hard, unless polynomial hierarchy collapses its third level. This based on similar result known constant-depth circuits and 2-local commuting gates (IQP).

Quantum coherence marks a deviation from classical physics, and has been studied as resource for metrology quantum computation. Finding reliable effective methods assessing its presence is then highly desirable. Coherence witnesses rely on measuring observables whose outcomes can guarantee that state not diagonal in known reference basis. Here we experimentally measure novel type of witness uses pairwise comparisons to identify superpositions basis-independent way. Our experiment single...