Photonicimplementationofbosonsampling:areview资源-CSDN文库

173 浏览量 2021-02-03 21:04:11 上传评论收藏 3.23MB PDF 举报

资源推荐

资源详情

资源评论

Photonic implementation of boson sampling:

a review

Daniel J. Brod,

Ernesto F. Galvão,

Andrea Crespi,

b,c

Roberto Osellame,

b,c

Nicolò Spagnolo,

* and

Fabio Sciarrino

Universidade Federal Fluminense, Instituto de Física, Niterói, Brazil

Consiglio Nazionale delle Ricerche, Istituto di Fotonica e Nanotecnologie, Milano, Italy

Politecnico di Milano, Dipartimento di Fisica, Milano, Italy

Sapienza Università di Roma, Dipartimento di Fisica, Roma, Italy

Abstract. Boson sampling is a computational problem that has recently been proposed as a candidate to

obtain an unequivocal quantum computational advantage. The problem consists in sampling from the

output distribution of indistinguishable bosons in a linear interferometer. There is strong evidence that such

an experiment is hard to classically simulate, but it is naturally solved by dedicated photonic quantum

hardware, comprising single photons, linear evolution, and photodetection. This prospect has stimulated

much effort resulting in the experimental implementation of progressively larger devices. We review recent

advances in photonic boson sampling, describing both the technological improvements achieved and the

future challenges. We also discuss recent propo sals and implementations of variants of the original problem,

theoretical issues occurring when imperfections are considered, and advances in the development of suitable

techniques for validation of boson sampling experiments. We conclude by discussing the futur e application of

photonic boson sampling devices bey ond the original theoretical scope.

Keywords: boson sampling; multiphoton interference; quantum supremacy; quantum simulation; integrated photonics.

Received Dec. 5, 2018; accepted for publication Mar. 25, 2019; published online May 9, 2019.

reproduction of this work in whole or in part requires full attribution of the original publication, including its DOI.

[DOI: 10.1117/1.AP.1.3.034001]

1 Introduction

In recent years, much work has been directed to the develop-

ment of suitable technologies for scalable quantum computa-

tion. This effort is motivated by the promise of quantum

algorithmic speed-up, with a notable early example provided

by Shor’s algorithm for integer factoring.

Despite the tremen-

dous advances in quantum technologies

2–7

reported in the last

few years, the implementation of a large-scale universal quan-

tum computer is still far from our current capabilities. Hence,

intermediate milestones need to be identified in the long-

term effort toward harnessing the computational potential of

quantum systems. A first fundamental step in this direction

would be the achievement of the regime of quantum computa-

tional supremacy,

i.e., the experimental demonstration of a

quantum device capable of performing a computational task

unambiguously faster than present-day classical computers.

Within this framework, Aaronson and Arkhipov (AA)

for-

mulated a well-defined computational problem that they called

boson sampling. This problem consists in sampling from the

output distribution of n indistinguishable bosons that interfere

during the evolution through a Haar-random-chosen linear

network. In Ref. 9, strong evidence was provided that boson

sampling is an intractable problem for classical computers, as

it is related to the evaluation of permanents of matrices with

complex entries (a problem known, in computational complex-

ity terms, to belong to the #P-hard class

). On the other hand,

boson sampling can be tackled with a dedicated quantum hard-

ware, which, despite not being universal for quantum computa-

tion, is capable of implementing the required dynam ics. To this

end, one of the most suitable platforms is provided by photonic

systems, as the necessary elements (sources, linear evolution,

and detection) are available with present technology.

Given

the lack of error-correction—an issue shared by all current

*Address all correspondence to Nicolò Spagnolo, E-mail: nicolo.spagnolo@

uniroma1.it

Review Article

Advanced Photonics 034001-1 May∕Jun 2019

•

Vol. 1(3)

proposals for quantum computational supremacy

—it is an open

question whether current technology is capable of scaling boson

sampling to arbitrarily large sizes while maintaining a quantum

advantage, which has also motivated research in more robust

variants of the model.

11–17

Following these theoretical develop-

ments, a strong experimental effort was then initiated to realize

progressively larger instances of boson sampling experiments.

This is leading to a race aimed at reachi ng the quantum

advantage

regime in a photonic platform, namely the condition

where the experiment is outper forming a classical computer. In

parallel, theoretical work was required to define suitable meth-

ods to verify that a given device is sampling from the correct

distribution.

This is indeed a relevant issue since the very com-

plexity of the problem forbids the application of usual verifica-

tion methods, and classical simulations become progressively

intractable for the incre asing system size.

In this paper, we discuss recent advances in the field of pho-

tonic boson sampling, with particular attention to experimental

implementations and validation methods. The remainder of this

paper is organized as follows. In Sec. 2, we first provide a theo-

retical overview on the problem, discussing the computational

model, classical simulation algorithms, and conditions that turn

the system amenable to efficient classical simulation. Then in

Sec. 3, we discuss variants of the original task that have been

proposed to improve the efficiency of the quantum simulator,

without affecting the problem’s complexity. In Sec. 4, we review

the experimental implementations reported so far, discussing the

employed photonic platforms. In Sec. 5, we provide an over-

view of the validation techniques for boson sampling that have

been proposed and tested experimentally. In Sec. 6, we then

discuss the scalability of photonic platforms toward achieving

the quantum supremacy regime. Finally, we provide an outlook

in Sec. 7, where we also discuss recently highlighted applica-

tions of boson sampling in contexts different from the original

proposal.

2 Boson Sampling: Theoretical Overview

In this section, we review the theoretical underpinnings of the

boson sampling problem. In Sec. 2.1, we define the problem and

discuss its computational complexity. In Sec. 2.2, we review the

known classical simulation algorithms, and in Sec. 2.3 we dis-

cuss some regimes, in which the classical simulation of boson

sampling is known to becom e tractable.

2.1 Model

Consider a set of m modes with associated creation operators

†

, for i ¼ 1; …;m, satisfying bosonic commutation relations.

A Fock state of n photons in these modes can be written as

jSi¼js

…s

i¼

i¼1

ða

†

j0i; (1)

where s

are the non-negative integers that count the number of

photons in each mode and

¼ n. When s

≤ 1 for all i, the

state is a no-collision state, meaning that there is no individual

mode containing two or more photons.

Consider now an m-mode linear-optical transformation (i.e.,

an interferometer) described by U ∈ SUðmÞ. Its action is fully

determined by the evolution of the creation operators:

†

→

j¼1

†

: (2)

It follows

9,20,21,22

that the transition probability between an in-

put state jSi¼js

…s

i and an output state jTi¼jt

…t

can be written as

Pr½S → T¼

jPerðU

S;T

Þj

!…s

!…t

; (3)

where U

S;T

is an n × n submatrix of U constructed by taking t

copies of the i’th row of U and s

copies of its j’th column,

and

PerðBÞ¼

σ∈S

i¼1

i;σðiÞ

(4)

is the permanent

of matrix B, and S

is the symmetric group.

Since the permanent is, in general, hard to compute,

Eq. (3)

underpins the complexity of a particular class of linear optical

experiments. In complexity theory terms, the permanent is

#P-hard,

and the best known classical algorithm for computing

it, due to Ryser, takes Oðn2

Þ steps for an n × n matrix. The

connection to complexity theory was noted by Troyansky

and Tishby

who attempted to leverage Eq. (3) to build a quan-

tum-mechanical algorithm to compute permanents. They real-

ized that their algorithm was not efficient, as exponentially

many experimental samples would be needed to produce a suf-

ficiently good approximation. AA explored this connection fur-

ther by shifting to sampling problems, where the computational

task is to produce a sample from some probability distribution

sufficiently close to the ideal one.

We now outline the argument

of AA, emphasizing the requirements it raises for experimental

demonstrations of boson sampling. Further developments that

attempted to soften the initial requirements are reviewed in

Sec. 3.

The standard boson sampling setup

consists of the following

ingredients (see Fig. 1).

(i) Preparation of a n-photon, m-mode input state, with each

mode containing either zero or one photon. Without loss of

generality, we can choose an input state with a single pho-

ton in each of the first n modes. Having more photons per

input mode means choosing repeated columns in the sub-

matrix of Eq. ( 3 ), which is likely to make the permanent

easier to compute (in the situation where all photons are

input in the same mode, the computation becomes trivial).

(ii) An m-mode interferometer described by an m-

dimensional Haar-random unitary operator U, where

m ¼ O ðn

Þ. An arbitrary interferometer can be built as

a circuit with Oðm

Þ two-mode elements and depth

OðmÞ.

23,24

Since only some input modes are occupied,

it is possible to reduce this further to a circuit of OðmnÞ

elements and depth Oðn log mÞ.

The randomness of U

has two main purposes. The first is so U does not have

any special structure that a classical simulation algorithm

could exploit. The second is that, for Haar-random uni-

taries in Oðn

Þ modes, the outcomes are dominated by

no-collision events due to the bosonic birthday paradox.

9,25

(iii) Photon detectors on every output. Given (ii), it suffices for

them to be bucket detectors, i.e., to only distinguish be-

tween vacuum and nonvacuum states.

Brod et al.: Photonic implementation of boson sampling: a review

Advanced Photonics 034001-2 May∕Jun 2019

•

Vol. 1(3)

Let D be the probability distribution predicted by quantum

mechanics for the no-collision outcomes of such an experiment,

and let k · k represent the total variation distance (TVD).

The main result of AA states (up to two additional complexity-

theoretic conjectures) that, if a classical algorithm existed that

could produce a sample from any distribution D

such that

kD − D

k < ϵ; (5)

in time polyðn; 1∕ϵÞ, the polynomial hierarchy (PH) would col-

lapse to the third level. Since PH is a tower of complexity classes

that is strongly believed to be infinite, the result of AA provides

strong evidence against the possibility of an efficient classical

simulation of boson sampling.

The proposal of AA uses an approximate notion of simula-

tion, as seen in Eq. (5). Thus one could attempt a classical sim-

ulation using an algorithm for approximating the permanent,

rather than Ryser’s exact algorithm. The problem with this ap-

proach is that it can be shown that the permanent would also be

#P-hard to approximate on the worst case

to the required pre-

cision. One classical algorithm to approximate the permanent is

due to Gurvits.

It takes time Oðn

∕ϵ

Þ to compute the perma-

nents of the n × n matrices in a boson sampling distribution to

precision ϵ. This is not sufficient to give a simulation of boson

sampling because there we typically have exponentially many

permanents that are exponentially small, and so approximating

them to a nontrivial precision via this algorithm would take

exponential time.

In very broad strokes, the argument of AA is as follows. If U

is a Haar-random matrix and m ¼ Oðn

Þ, it can be proven that

n × n submatrices of U look approximately Gaussian. Since

Gaussian matrices do not seem to possess any special structure

that a classical algorithm could exploit, it is reasonable to con-

jecture that, with high probability, the permanent of a Gaussian

matrix is among the hardest ones to compute (this is the perma-

nent-of-Gaussians conjecture). However, if a classical algorithm

could sample from a distribution ϵ-close in TVD to the ideal

one, it would have to be approximating most probabilities very

well. Using an algorithm attributable to Stockmeyer,

it would

then be possible to solve a #P-hard problem inside BPP

, which

is a complexity class that resides inside the third level of the PH.

Using a theorem due to Toda,

this would imply that the entire

hierarchy would have to collapse to its third level. This result,

thus, establishes that boson sampling is hard to simulate, even

in an approxi mate sense, up to three conjectures that: (i) PH is

infinite, (ii) permanents of Gaussian matrices are #P-hard to

approximate, and (iii) permanents of Gaussian matrices are

not too concentrated around zero. The third conjecture is

more technical but is necessary to relate two versions of the

problem of approximating permanents of Gaussian matrices:

to within additive and multiplicative errors.

2.2 Simulation Algorithms

The AA argument provides evidence that any boson sampling

simulation on a classical computer must take a time which

grows exponentially with the number of photons n. It is impor-

tant to find the best classical algorithms for boson sampling

simulation. This will help to establish the goals for experimen-

tally demonstrating unequivocal quantum computational advan-

tage. From a more practical point of view, simulation algorithms

are required for analyzing current, small-scale implementations.

Optimal simulation algorithms also help clarify how inevitable

experimental imperfections affect the computational power of

the model; this includes partial photon distinguishability and

photon loss. In this section, we review known classical simula-

tion algorithms for boson sampling.

The brute-force approach for simulating boson sampling

would involve calculating the probabilities associated with all

input–output possibilities (in case we are using the variable-

input, scattershot approach to boson sampling, see Sec. 3.1).

Doing this for n photons in m ¼ n

modes with Ryser’s algo-

rithm, and for all





input–output combinations, would take

Oðn2





time steps. As regards space (memory) usage, it is

not necessary to store all calculated permanents.

This brute-

force approach is computationally intensive in the extreme;

we now review recently proposed algorithms that have consid-

erably improved on this.

(a) (b)

Fig. 1 Boson sampling and its corresponding photonic implementation. (a) Conceptual scheme of

the boson sampling task. The output probabilities after the scattering process are related to the

evaluation of permanents of n × n submatrices of U , obtained by selecting rows and column of the

matrix U describing the linear transformation. A classical simulation then requires the evaluation of

hard-to-compute matrix permanents. (b) Photonic approach to building a quantum device that

solves the boson sampling task. The three main building blocks are: (i) n photon sources for input

state generation, (ii) m-mode linear interferometer, composed of beam splitters and phase

shifters, implementing the selected unitary transformation U, and (iii) detectors on each of the

output modes.

Brod et al.: Photonic implementation of boson sampling: a review

Advanced Photonics 034001-3 May∕Jun 2019

•

Vol. 1(3)

剩余13页未读，继续阅读

评论收藏

内容反馈

weixin_38641111

粉丝: 1
资源: 931

Photonic implementation of boson sampling: a review

boson试验报告

Photonic tractor beams: a review

光子神经网络综述 A Review of Photonic Neural Networks

PC.rar_photonic crystals

用matlab生成谐波代码-Photonic_Force_Microscopy:非球形颗粒的PFM校准

comsol_photonic_crystal_fibre_comsol_

Photonic generation of microwave signal using a dual-wavelength erbium-doped fiber ring laser with CMFBG filter and saturable absorber

Integrated optical delay lines: a review and perspective [Invited]

Foundations of Photonic Crystal Fibres.pdf

RF photonic technology in optical fiber links.pdf

Shun-Lien-Chuang-Physics-of-Photonic-Devices-Wile_Shun lien Chua

Photonic Crystal Fibers---Properties and Applications

Application of FPGA to real-time machine learning

photonic-bandgap-comsol-matlab-master_photonic_photoniccomsol_ba

Signal-to-Noise Ratio of Dispersive Photonic Signal Processors

Experimental demonstration of one-way slow wave in waveguide involving gyromagnetic photonic crystals

Photonic angle-of-arrival and time-dif ference-of-arrival measurement based on dual drive 1 \times 2 MZM

Nonreciprocal transmission in a nonlinear photonic

High speed phase modulators for silicon photonic integrated circuits: a role for lithium niobate

1830 Photonic Service Switch

Photonic Crystals.pdf

Photonic crystal fibres

Thermally tuning of the photonic band gap of SiO2 colloid crystal infilled with ferroelectric BaTiO3

guangzijingti.rar_Photonic crystal_photonic fiber_光子晶体_光子晶体 matl

The phase control of spontaneous emission from a microwave-driven three-atom embedded in Photonic Crystals

Photonic Analog-to-Digital Conversion of Time-Continuous Signals using a TDM Switching-Wavelength Sampling Source

最新资源