A certification scheme for the boson sampler

Kai Liu; Austin Peter Lund; Yong-Jian Gu; Timothy Cameron Ralph

doi:10.1364/JOSAB.33.001835

Journal of the Optical Society of America B
Vol. 33,
Issue 9,
pp. 1835-1841
(2016)
•https://doi.org/10.1364/JOSAB.33.001835

A certification scheme for the boson sampler

Kai Liu, Austin Peter Lund, Yong-Jian Gu, and Timothy Cameron Ralph

Open Access

Get PDF
Email
Share
Get Citation
Copy Citation Text
Kai Liu, Austin Peter Lund, Yong-Jian Gu, and Timothy Cameron Ralph, "A certification scheme for the boson sampler," J. Opt. Soc. Am. B 33, 1835-1841 (2016)

Export Citation
- BibTex
- Endnote (RIS)
- HTML
- Plain Text
Citation alert
Save article
Spotlight Summary

More Like This

Experimental hybrid quantum-classical reinforcement learning by boson sampling: how to train a...
Jan Jašek, et al.
Opt. Express 27(22) 32454-32464 (2019)

Optimality of quantum randomness certification with independent devices
Xin-Wei Fei, et al.
J. Opt. Soc. Am. B 35(9) 2186-2191 (2018)

Engineering continuous and discrete variable quantum vortex states by nonlocal photon subtraction...
David Barral, et al.
J. Opt. Soc. Am. B 33(11) 2225-2235 (2016)

Related Topics
Table of Contents Category
- Quantum Optics
Optics & Photonics Topics
?

The topics in this list come from the Optics and Photonics Topics applied to this article.

About this Article
History
- Original Manuscript: April 13, 2016
- Revised Manuscript: June 30, 2016
- Manuscript Accepted: July 22, 2016
- Published: August 9, 2016
Virtual Issues
September 12, 2016 Spotlight on Optics

Abstract

Boson sampling can provide strong evidence that the computational power of a quantum computer outperforms a classical one via currently feasible linear optics experiments. However, how to identify an actual boson sampling device against any classical computing imposters is an ambiguous problem due to the computational complexity class in which boson sampling lies. The certification protocol based on bosonic bunching fails to rule out the so-called mean-field sampling. We propose a certification scheme to distinguish the boson sampling from the mean-field sampling for any random scattering matrices chosen via the Harr measure. We numerically analyze our scheme and the influence of the imperfect input states caused by non-simultaneous arrival photons.

1. INTRODUCTION

A major goal in quantum information is the implementation of a genuine and universal quantum computer that can solve computational tasks beyond the power of a classical computer. This goal, however, faces huge challenges because current technology cannot maintain coherence long enough to perform a full computation potentially involving a large number of qubits. Several quantum algorithms, such as Shor’s factoring algorithm [1,2], can compute certain problems for which there are no known classical algorithms with polynomial time complexity. However, the near-term prospects for Shor’s factoring algorithm to overturn the central role of the extended Church–Turing thesis [3] in classical computer science are low due to the difficultly of its experimental realization [4].

Boson sampling provides a different path toward showing the increased power of quantum computation [5]. The complexity of boson sampling is believed to exceed that of Shor’s factoring algorithm. If a classical algorithm existed to sample the BosonSampling distribution, even in an approximate sense, it would lead the polynomial hierarchy to collapse to the third level, something that is believed not to occur. Experimental boson sampling with up to six photons has been reported, demonstrating the theoretical prediction of the output distribution [6–10]. Temporal encoding has been used to extend the number of scattering modes to ten, with the potential to be extended much further [11,12]. In addition, research on sampling from closely rated distributions has extended our knowledge about the nature of boson sampling [13–15].

While the hardness of boson sampling is its key feature, the hardness of boson sampling requires that the certification of its output is not easy. This is because boson sampling is in a class of problems that is larger than the class NP (which Shor’s algorithm belongs to). This leaves room for a classically efficient sampling algorithm to fake the boson sampling distribution in a way that is not efficiently detectable. This has motivated the recent study of different strategies to certify the boson sampling distribution against alternative distributions that attempt to deceive a verifier. The validation test of Aaronson and Arkhipov discriminates the boson sampling distribution against the uniform one within a constant number of samples [16–18]. Another protocol based on the tendency for bosons to bunch together in interferometers rules out the classical sampling distribution, which uses distinguishable photons as input to the sampler [19,20]. A so-called mean-field sampler [21] invalidates these strategies by replicating the characteristic bosonic bunching behavior, and this type of sampling has been experimentally performed [22]. Although this certification scheme was proposed to rule out plausible physical models by observing if some forbidden events occur in the output modes, its effective range is strictly limited to the symmetric situation in which we need to artificially construct a boson sampler with a cyclic-symmetry initial state and an interaction described by a Fourier matrix [21].

In this paper, we describe a certification scheme that can rule out mean-field sampling devices from the true boson sampling without changing the internal working of the device and uses the same distribution of the input transformation matrices as required for true boson sampling. The model we use for a potential boson sampling device is as a black box whose detailed internal functioning is unknown. The black box takes as an input a Harr-random unitary transformation matrix and an input Fock state described by a sequence of zeros and ones. The device outputs Fock basis measurement results, which are sequences of integers. In our certification protocol, we inject a test input state consisting of single photons into every mode. The mean-field sampling devices produce uniform distributions for this test state, and true boson sampling does not. It is then possible to distinguish a boson sampler from a mean-field sampler via analyzing the variations in the output probability distribution. We also analyze the noise characteristics for partially distinguishable particles in our certification scheme.

2. SAMPLING MODELS

A. Boson Sampling

An ideal boson sampler scatters $n$ indistinguishable photons by an $N$ -port interferometer of lossless, linear optical elements, i.e., phase shifters and beam splitters, and counts the number of photons exiting from each output mode. The input state is a Fock state with definite numbers of photons occupying each mode, which is expressed by

S_{B} = | s_{1}, s_{2}, \dots, s_{N} ⟩ = \prod_{j = 1}^{N} \frac{{({\hat{a}}_{j}^{†})}^{s_{j}}}{\sqrt{s_{j}!}} | 0 ⟩ = \frac{{(a_{1}^{†})}^{s_{1}} {(a_{2}^{†})}^{s_{2}} \dots {(a_{N}^{†})}^{s_{N}}}{\sqrt{s_{1}! s_{2}! \dots s_{N}!}} | 0 ⟩,

where

s_{j}

represents the number of photons prepared on the

j

th input mode,

\sum_{j = 1}^{N} s_{j} = n

{\hat{a}}_{j}^{†}

is the creation operator for the

j

th input mode, and

| 0 ⟩

is the vacuum state. We also define an equivalent alternative notation

j⃗ = (j_{1}, j_{2}, \dots, j_{n})

for the mode arrangement of input photons, where

j_{i}

is the mode occupied by the

i

th photon and

1 \leq j_{i} \leq N

The dimensionality of a unitary transformation $\hat{S}$ between the input and output state vectors will increase exponentially as $n$ and $N$ grow. However, when restricting the transformations to those of linear optical elements, the transformation can be represented by an $N \times N$ complex unitary matrix $Λ$ , which describes the scattering of photons. One can write this transformation down in terms of the Heisenberg evolution of the creation operators as

\hat{S} {\hat{a}}_{j}^{†} {\hat{S}}^{†} = \sum_{k = 1}^{N} Λ_{k, j} {\hat{a}}_{k}^{†},

which is a linear transformation of the creation operators (hence the name). After the linear scattering transformation, a measurement is performed in the Fock basis. The probability of detecting the event

T_{B} = | t_{1}, t_{2}, \dots, t_{N} ⟩

, whose mode arrangement is

k⃗ = (k_{1}, k_{2}, \dots, k_{n})

, from the output ports is

P_{B} (T_{B}; S_{B}, Λ) = \frac{{| Permanent (A) |}^{2}}{\prod_{i = 1}^{N} s_{i}! t_{i}!},

where

A

is a submatrix of

Λ

with elements

A_{q, p} = Λ_{k_{q}, j_{p}}

, and the input mode arrangement

j⃗

is defined similarly to the output mode arrangement

k⃗

. The computational task of boson sampling is then defined as producing samples for the output events with the correct probabilities for any given

Λ

The hardness of boson sampling is shown by using the boson sampling process to make approximations of the permanent of a matrix. The proof depends on some plausible conjectures about approximating the permanents of i.i.d. Gaussian matrices [5]. To be close to the Gaussian matrices, it is desirable to choose $Λ$ randomly according to the Harr measure on $N \times N$ unitary matrices and for $N$ to scale at least as $n^{2}$ . Physically, it requires that the scattering process is arbitrarily tunable to perform the corresponding transformation $Λ$ . With lossless optical elements and efficient photon detectors, a physically constructed boson sampler would accurately generate samples from this probability distribution. The existence of a classical algorithm that simulates such a quantum device in polynomial time would imply a collapse in the polynomial hierarchy [5]. The collapse of the polynomial hierarchy has quite a technical definition, but essentially, a collapse of the hierarchy is akin to a statements of the form $P = N P$ , but depending on exactly which level the hierarchy collapses, the weaker the statement is about the relationship between $P$ and $N P$ . Nevertheless, it is believed that the hierarchy does not collapse at any level, and therefore, the boson sampling problem is hard for any classical algorithm.

B. Classical Sampling

One way to construct a classical analog of boson sampling is to take as an input distinguishable photons instead of indistinguishable photons. Given an input state $S_{D} = (s_{1}, s_{2}, \dots, s_{N})$ , the probability to detect the output configuration $T_{D} = (t_{1}, t_{2}, \dots, t_{N})$ is

P_{D} (T_{D}; S_{D}, Λ) = \frac{Permanent (Ω)}{\prod_{i = 1}^{N} \sqrt{s_{i}! t_{i}!}},

where each element in the matrix

Ω

is the absolute square of the corresponding element in matrix

A

Ω_{q, p} = {| A_{q, p} |}^{2}

. Aaronson and Arkhipov showed that sampling from this distribution is possible classically using a polynomial time algorithm [5]. This result is consistent with the fact that estimating the matrix permanent of matrices with all positive entries can be performed using a classical polynomial time algorithm [23].

C. Mean-Field Sampling

The mean-field sampler devised by Tichy et al. [21] is an efficiently computable and physically plausible model of a boson sampler imposter. The interference of Bose–Einstein condensates motivates the physical implementation of the mean-field sampler, which provides an efficient approximation for the probability distribution of the boson sampling. The input state $S_{M f}$ is a set of $n$ identical single-photon states

| ψ ⟩ = \frac{1}{\sqrt{n}} \sum_{p = 1}^{n} e^{i θ_{p}} {\hat{a}}_{j_{p}}^{†} | 0 ⟩,

where the relative phase

θ_{p}

is randomly chosen from 0 to

2 π

, and the subscript

j_{p}

corresponds to the mode arrangement

j⃗

of the boson sampler’s input state and denotes the

j_{p}

th input mode. Each single photon propagates through the linear scattering apparatus and evolves to the state

\hat{S} | ψ ⟩ = \frac{1}{\sqrt{n}} \sum_{p = 1}^{n} e^{i θ_{p}} \hat{S} {\hat{a}}_{j_{p}}^{†} {\hat{S}}^{†} | 0 ⟩ = \frac{1}{\sqrt{n}} \sum_{k = 1}^{N} \sum_{p = 1}^{n} e^{i θ_{p}} Λ_{k, j_{p}} {\hat{a}}_{j_{p}}^{†} | 0 ⟩ .

On the side of output ports, each photon would be detected on the $k$ th mode with the probability

p_{k} = \frac{1}{n} {| \sum_{p = 1}^{n} e^{i θ_{p}} Λ_{k, j_{p}} |}^{2} .

Injecting $n$ single-photon states as per Eq. (5) into the scattering setup shot by shot, we can detect the output event $T_{M f} = (t_{1}, t_{2}, \dots, t_{N})$ , whose mode arrangement is $k⃗ = (k_{1}, k_{2}, \dots, k_{n})$ , with the probability

P_{M f} (T_{M f}; S_{M f}, Λ) = (\begin{matrix} n \\ t_{1} \end{matrix}) (\begin{matrix} n - t_{1} \\ t_{2} \end{matrix}) \dots (\begin{matrix} t_{N} \\ t_{N} \end{matrix}) p_{1}^{t_{1}} p_{2}^{t_{2}} \dots p_{N}^{t_{N}} = \frac{n!}{n^{n} \prod_{l = 1}^{N} t_{l}!} \prod_{k = 1}^{N} {| \sum_{p = 1}^{n} e^{i θ_{p}} Λ_{k, j_{p}} |}^{2 t_{k}} = \frac{n!}{n^{n} \prod_{l = 1}^{N} t_{l}!} \prod_{q = 1}^{n} {| \sum_{p = 1}^{n} e^{i θ_{p}} Λ_{k_{q}, j_{p}} |}^{2} .

In our case, we supposed the relative phases $θ_{p}$ with the same subscript $p$ among these single-photon states were identical but would be randomly regenerated for the next run of sampling. Repeatedly running the sampler time after time, we will get the average probability by integrating $θ_{p}$ as

{\tilde{P}}_{M f} (T_{M f}; S_{M f}, Λ) = \int_{0}^{2 π} \frac{d θ_{1}}{2 π} \dots \int_{0}^{2 π} \frac{d θ_{n}}{2 π} P_{M f} (T_{M f}; S_{M f}, Λ) = \frac{n!}{n^{n} \prod_{l = 1}^{N} t_{l}!} \prod_{q = 1}^{n} \sum_{p = 1}^{n} {| Λ_{k_{q}, j_{p}} |}^{2} .

D. Coherent-State Sampling

As the name implies, the coherent-state sampler takes the input as a product of coherent states $S_{C s} = | e^{i χ_{1}} | α_{1} |, e^{i χ_{2}} | α_{2} |, \dots, e^{i χ_{N}} | α_{N} | ⟩$ , where $| α_{j} |$ is the amplitude of the state, and $χ_{j}$ is the relative phase randomly chosen from 0 to $2 π$ . To implement the coherent-state sampler, one only needs a source of coherent light from a laser which is split into $N$ modes, which results in the required value of $α_{j}$ . This is, generally speaking, easier than preparing many indistinguishable single-photon states. After propagating through the linear scattering unitary, the transformation of coherent states is

\hat{S} S_{C s} = \exp (- \frac{1}{2} \sum_{j = 1}^{N} {| α_{j} |}^{2}) \exp (\sum_{k = 1}^{N} \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} {\hat{a}}_{k}^{†}) | 0 ⟩ .

The state of the output ports is still a product of the coherent states. After renormalization, the final state is

\hat{S} S_{C s} = \otimes_{k = 1}^{N} \exp (- \frac{1}{2} {| \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} |}^{2}) \exp (\sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} {\hat{a}}_{k}^{†}) | 0 ⟩ = \otimes_{k = 1}^{N} \exp (- \frac{1}{2} {| \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} |}^{2}) \sum_{n_{k} = 0}^{\infty} \frac{{(\sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j})}^{n_{k}}}{\sqrt{n_{k}!}} | n_{k} ⟩ .

The probability to detect the output Fock state $T_{C s} = (t_{1}, t_{2}, \dots, t_{N})$ is

P_{C s} (T_{C s}; S_{C s}, Λ) = \exp (- \sum_{k = 1}^{N} {| \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} |}^{2}) \prod_{k = 1}^{N} \frac{{| \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} |}^{2 t_{k}}}{t_{k}!} .

After averaging over the random phase $χ_{j}$ , the probability becomes

{\tilde{P}}_{C s} (T_{C s}; S_{C s}, Λ) = \exp (- \sum_{k, j = 1}^{N} {| α_{j} Λ_{k, j} |}^{2}) \prod_{k = 1}^{N} \frac{{(\sum_{j = 1}^{N} {| α_{j} Λ_{k, j} |}^{2})}^{t_{k}}}{t_{k}!} .

Using the probabilities in Eqs. (3), (4), (8), and (12), we have simulated boson sampling, classical sampling, mean-field sampling, and coherent-state sampling in the cases of two and three photons averaging over 100 Harr-random unitary matrices, as depicted in Fig. 1. The counting statistics of boson sampling is similar to mean-field sampling, while classical sampling obviously behaves higher on coincidence outcomes but lower on those with multiply populated modes. This phenomenon implies that mean-field sampling and coherent-state sampling abide by the bunching tendency of boson sampling. In the simulation, we set the input state of the coherent-state sampler to $α_{j} = 1$ on those modes that would have a single photon input and $α_{j} = 0$ for those modes that would have been a vacuum. As the coherent state has an indefinite number of photons, there are many events output from the coherent-state sampler that are not exactly two-photon or three-photon events in the respective simulations. The coherent-state sampler therefore yields many events containing more or less photons in total, and these events are not shown in Fig. 1. When compared with boson sampling, the counting statistics of the events shown for the coherent-state sampler is consequently lower.

Fig. 1. Simulation of boson sampling, mean-field sampling, coherent-state sampling, and classical sampling for (a) two photons with input state $S = (0, 1, 1, 0)$ , and (b) three photons with input state $S = (0, 1, 1, 1, 0)$ . Both cases run over 100 Harr-random matrices and are sampled 100 times for each matrix.

Download Full Size | PDF

3. CERTIFICATION PROTOCOL

A. Certification via the $N$ Photon Single-Photon Input State

Since the certification based on bosonic bunching does not distinguish between boson sampling and the mean-field sampling, Tichy et al. [21] proposed a scheme using a symmetric Fourier matrix and a particular initial state with cyclic symmetry. In their scheme, some forbidden outcomes in the boson sampling will occur in the mean-field sampling. However, their scheme has the obvious disadvantage that it must change the sampling method and deviates from the standard boson sampling construction.

Suppose there is a sampling algorithm where the output can be measured, and the input is a linear unitary interaction of single photons and vacuum states. It is assumed that no details of the internal workings of the implementation of the algorithm are known. Is it possible to identify whether this sampler is a fully quantum boson sampler or a possibly classical mean-field sampler? In this paper, we present numerical evidence that inputting a test state that is constructed from single photons can solve this problem. The test state of the boson sampler is $S_{T} = (1, 1, \dots, 1)$ , whose mode arrangement is $j⃗ = (1, 2, \dots, N)$ . A correspondingly complex test state for the mean-field sampler is $N$ runs using a single-photon state prepared as $| ψ ⟩ = \frac{1}{\sqrt{N}} \sum_{l = 1}^{N} e^{i θ_{l}} {\hat{a}}_{l}^{†} | 0 ⟩$ . In this case, the sum term in Eq. (9) becomes $\sum_{l = 1}^{N} {| Λ_{k_{q}, l} |}^{2}$ , which is equal to 1 as $Λ$ is unitary. Thus, given the test state as the input state of a mean-field sampler, the outcome $T_{M f}$ will be detected with the probability

{\tilde{P}}_{M f} (T_{M f}; S_{T}, Λ) = \frac{n!}{n^{n} \prod_{k = 1}^{N} t_{k}!} .

From this expression, we can see that the probability distribution is not a function of the unitary matrix $Λ$ , but only a function of the number of photons $n$ and the output configuration $T_{M f}$ . Since the number of photons is equal to the number of input modes, the probability distribution is determined only by the dimension of the unitary matrix. The invariance of this distribution with respect to changes in the unitary matrix suggests that there exists an efficient method for discrimination between the mean-field sampler and the fully quantum boson sampler [17]. Here we study numerically a scenario with small numbers of photons where the entire probability distribution can be feasibly studied.

In Fig. 2, we randomly selected four $4 \times 4$ unitary matrices by the Harr measure and numerically simulated boson sampling and mean-field sampling with the test input state $S_{T} = (1, 1, 1, 1)$ . The number of samples simulated for all situations is 10,000. The counting statistics of the mean-field sampling present as relatively uniform when compared with boson sampling in agreement with the theory above. The sample size here is not large enough for the effect of the randomly varying relative phase $θ_{l}$ to completely vanish, so the counting statistics of mean-field sampling do not completely satisfy the probability given in Eq. (14). Fortunately, the sampling statistic of the mean-field sampler approximates the uniform distribution in the case of an arbitrary unitary matrix, while the sampling statistics of the boson sampler will vary for different matrices. For a particular matrix, the difference between the maximum event and the minimum event in boson sampling statistics is larger than those in the relatively uniform mean-field sampling. By using this particular test state as an input, the distributions of boson sampling and mean-field sampling can be distinguished without needing to modify the sampler, even without any prior knowledge about the linear scattering matrix.

Fig. 2. Simulation of boson sampling and mean-field sampling with the test state $S_{T} = (1, 1, 1, 1)$ . Each panel represents a different choice of a Harr-random unitary matrix. For each choice of unitary matrix, 10,000 samples are taken. For this quantity of samples, the maximum standard deviation of the number of samples is 50. There are cases in each panel for which the number of events sampled deviate between the two cases by 5 to 10 standard deviations.

Download Full Size | PDF

In fact, when returning to the case where the input state does not have all modes occupied by a single photon, the most likely event still occurs in the boson sampling distribution and not the mean-field distribution when a large number of samples are taken, as shown in Fig. 3. One can firmly believe that the highest sampled event is from the boson sampling distribution. We conjecture the reason is that random phase of input states for the mean-field sampler limits the maximum value in probability distribution. However, this method may need a number of samples that depends exponentially on the number of input photons, and so this may be an inefficient protocol to distinguish the boson sampling and mean-field distributions.

Fig. 3. Simulation of boson sampling and mean-field sampling with the input state $S = (0, 1, 1, 0)$ . We chose four random matrices by the Harr measure and sampled them 10,000 times for each matrix. The same expected variation as in Fig. 2 applies to these data.

Download Full Size | PDF

Our verification protocol can be compared and contrasted with those described in the introduction [17,21]. One can see that this protocol is different from these previous ones but has some related structures. The protocol in [17] tests if the output distribution is uniform in the 0 and 1 subspace of detections or if it is a true boson sampling distribution proportional to matrix permanents. This protocol is efficient and stays completely within the boson sampling model of $n$ photons into $N > n^{2}$ modes. It can, however, be efficiently deceived with the classical sampling distribution. The protocol of [21] deviates from the standard boson sampling model but, given some assumptions about the nature of the linear interaction, is an efficient test of a necessary condition to perform boson sampling. In particular, it has the ability to perform non-classical interference. Our protocol also deviates from the standard boson sampling, but in a much simpler way than that in [21]. We add more photons to the input state so that all input modes contain single photons. In this case, one is now in the regime of [17], where to discriminate the mean-field sampler and boson sampling, one must distinguish uniformity from non-uniformity. When applying our criterion to a distribution that does scatter into $N > n^{2}$ modes, the distinction between the maximal and minimally sampled events still exists, but as stated above, one may need to gather an exponentially scaling number of samples to distinguish these distributions. Depending on the cost of single photons relative to the modes, it may be desirable to work in the small photon number regime and take an exponential number of samples to perform our test instead of using the $N = n$ case. It also must be remembered that no single test can efficiently verify the device’s proper functioning as a boson sampler, as this is believed to not be possible [5].

B. Robustness for the Partially Distinguishable Boson Sampling

Boson sampling in practice is expected to be influenced by experimental inaccuracies in the inputting, scattering, and detecting of single photons. We now consider the case of imprecision in preparing input states. In particular, we consider input states to the boson sampler constructed from partially distinguishable photon states. In this analysis, the degree of freedom used to induce distinguishability is the mutual delay of injected photons. The theory we use to describe this effect considers orthogonal spatio-temporal modes. By performing a Gram–Schmidt orthogonalization on the spatio-temporal degrees of freedom of the input state, the single particle in each mode can be represented as

{\hat{a}}_{j_{r}}^{†} = \sum_{k = 1}^{j_{r}} C_{r, k} {\hat{a}}_{j_{r}, t_{k}}^{†},

where the coefficients satisfy normalization such that

\sum_{k = 1}^{j_{r}} {| C_{j_{r}, k} |}^{2} = 1

, and the single-photon states are orthonormalized as

⟨ 0 | {\hat{a}}_{p, t_{m}} {\hat{a}}_{q, t_{n}}^{†} | 0 ⟩ = δ_{p, q} δ_{m, n}

. Here the double subscript represents the spatial and temporal mode labels, respectively. In this notation, we consider the temporal degree of freedom to form an orthonormal basis of arriving time

{| t_{1} ⟩, | t_{2} ⟩, \dots, | t_{j_{r}} ⟩}

; the input state can be expressed as [21,24]

| S_{B} ⟩ = {\hat{a}}_{j_{1}, t_{1}}^{†} \sum_{k_{2} = 1}^{2} \sum_{k_{3} = 1}^{3} \dots \sum_{k_{n} = 1}^{n} \prod_{r = 2}^{n} C_{r, k_{r}} {\hat{a}}_{j_{r}, t_{k_{r}}}^{†} | 0 ⟩ .

This equation can be qualitatively understood as mode 1 defining a basis into which all other modes are compared, so the first mode is the “pure” mode. The second mode then has some common overlap with the first mode and hence can be divided up into two components that overlap with the first mode and some other orthogonal components that result in the sum over the modes only being required up to two. The third mode in which a photon is created will then have some components that overlap with the first and second modes and then an orthogonal component, which means there will be three terms in this sum, and so on in this manner until all photons have been expanded. The terms that have identical subscripts $t_{k_{r}}$ describe an input state of temporally indistinguishable photons, which relates to a standard boson sampling. The term with the different subscript $t_{k_{r}}$ corresponds to a classical sampling with distinguishable particles. The complex case is terms with some identical and some different $t_{k_{r}}$ , which relates to the partially distinguishable boson sampling. Adjusting the coefficient $C_{r, k_{r}}$ , the input state gives rise to a sampling in the range from fully indistinguishable to fully distinguishable particles.

By injecting the test state $S_{T} = (1, 1 \dots 1)$ , we still can differentiate the mean-field sampling from the partially distinguishable boson sampling. As shown in Fig. 4, we simulate the partially distinguishable boson sampling and the mean-field sampling with the test state $S_{T} = (1, 1, 1)$ . For the partially distinguishable boson sampling, the fluctuations vary considerably depending on random matrices, while mean-field sampling presents a stable distribution.

Fig. 4. Simulation of boson sampling, classical sampling, partially distinguishable boson sampling, and mean-field sampling with the input state $S = (1, 1, 1)$ . Four randomly chosen matrices are displayed, with 10,000 samples for each case. We chose the coefficients for the Fock basis state in Eq. (16) to be identical, i.e., $\frac{1}{\sqrt{6}}$ , as there are 6 Fock basis states in this example. In terms of two-photon interference, this is equivalent to having a 50% probability of finding that the input particles were indistinguishable.

Download Full Size | PDF

4. CONCLUSIONS

Boson sampling with identical bosons provides evidence that quantum computers can outperform classical computers. However, its verification is known to be difficult due to its computational complexity being outside the class $N P$ . In our paper, we have proposed a certification scheme for the specific case of discriminating the boson sampler from the mean-field sampler. Without any limitation on the scattering matrices, the protocol only needs to prepare a test state and primitively analyze the output probability distribution. We have numerically simulated samples of the boson sampling and the mean-field sampling distributions when inputting the test state. For the output probability distributions, the statistics of boson sampling fluctuate more significantly than mean-field sampling. Considering the influence of imperfect input states, we have shown the certification capability of the protocol for partially distinguishable boson sampling against mean-field sampling.

In summary, we describe an experimental approach to verify the actual boson sampling against a physically plausible imposter. Compared to previous methods, our scheme retains a scattering matrix randomly chosen by the Harr measure and continues to work under the noise of partial distinguishability caused by non-simultaneously arriving photons. This work does not address the efficiency problem of our scheme. Optimizing the scheme to reduce the number of samples needed will be the direction of our future work.

Funding

National Natural Science Foundation of China (NSFC) (11475160, 61575180); Natural Science Foundation of Shandong Province (ZR2014AQ026, ZR2014AM023); Fundamental Research Funds for the Central Universities of China (201313012); China Scholarship Council (CSC) (201306330035); National Key Laboratory of Electromagnetic Environment (201500005); Australian Research Council (ARC) (CE110001027).

REFERENCES

1. P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994), pp. 124–134.

2. P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Rev. 41, 303–332 (1999). [CrossRef]

3. M. A. Nielsen and I. L. Chuang, Quantum Computation and Information (Cambridge University, 2000).

4. E. Martin-Lopez, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling,” Nat. Photonics 6, 773–776 (2012). [CrossRef]

5. S. Aaronson and A. Arkhipov, “The computational complexity of linear optics,” in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2011, pp. 333–342.

6. M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, “Photonic boson sampling in a tunable circuit,” Science 339, 794–798 (2013). [CrossRef]

7. J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339, 798–801 (2013). [CrossRef]

8. M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nat. Photonics 7, 540–544 (2013). [CrossRef]

9. A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nat. Photonics 7, 545–549 (2013). [CrossRef]

10. J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science 349, 711–716 (2015). [CrossRef]

11. K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde, “Scalable boson sampling with time-bin encoding using a loop-based architecture,” Phys. Rev. Lett. 113, 120501 (2014). [CrossRef]

12. Y. He, Z.-E. Su, H.-L. Huang, X. Ding, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, X.-L. Wang, C. Schneider, M. Kamp, S. Höfling, C.-Y. Lu, and J.-W. Pan, “Scalable boson sampling with a single-photon device,” arXiv:1603.04127 [quant-ph] (2016).

13. P. P. Rohde and T. C. Ralph, “Error tolerance of the boson-sampling model for linear optics quantum computing,” Phys. Rev. A 85, 022332 (2012). [CrossRef]

14. A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, “Boson sampling from a Gaussian state,” Phys. Rev. Lett. 113, 100502 (2014). [CrossRef]

15. M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvãoand, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino, “Experimental scattershot boson sampling,” Sci. Adv. 1, e1400255 (2015). [CrossRef]

16. C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, “Boson-sampling in the light of sample complexity,” arXiv:1306.3995v2 (2013).

17. S. Aaronson and A. Arkhipov, “BosonSampling is far from uniform,” Quantum Inf. Comput. 14, 1383–1423 (2013).

18. N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014). [CrossRef]

19. J. Carolan, D. A. MeineckeJasmin, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, “On the experimental verification of quantum complexity in linear optics,” Nat. Photonics 8, 621–626 (2014). [CrossRef]

20. J. Carolan, J. Meinecke, P. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. Thompson, J. L. O’Brien, J. Matthews, and A. Laing, “Verifying quantum complexity in linear optical experiments,” in Conference on Lasers and Electro-Optics (Optical Society of America, 2014), paper FM2A.7.

21. M. C. Tichy, K. Mayer, A. Buchleitner, and K. Mølmer, “Stringent and efficient assessment of boson-sampling devices,” Phys. Rev. Lett. 113, 020502 (2014). [CrossRef]

22. A. Crespi, R. Osellame, R. Ramponi, M. Bentivegna, F. Flamini, N. Spagnolo, N. Viggianiello, L. Innocenti, P. Mataloni, and F. Sciarrino, “Suppression law of quantum states in a 3D photonic fast Fourier transform chip,” Nat. Commun. 7, 10469 (2016). [CrossRef]

23. M. Jerrum, A. Sinclair, and E. Vigoda, “A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,” in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), New York, 2001, pp. 712–721.

24. M. C. Tichy, H. T. Lim, Y. S. Ra, F. Mintert, Y. H. Kim, and A. Buchleitner, “Four-photon indistinguishability transition,” Phys. Rev. A 83, 062111 (2011). [CrossRef]

Previous Article Next Article

Cited By

Optica participates in Crossref's Cited-By Linking service. Citing articles from Optica Publishing Group journals and other participating publishers are listed here.

Alert me when this article is cited.

Fig. 1. Simulation of boson sampling, mean-field sampling, coherent-state sampling, and classical sampling for (a) two photons with input state

S = (0, 1, 1, 0)

, and (b) three photons with input state

S = (0, 1, 1, 1, 0)

. Both cases run over 100 Harr-random matrices and are sampled 100 times for each matrix.

View in Article | Download Full Size | PDF

Fig. 2. Simulation of boson sampling and mean-field sampling with the test state

S_{T} = (1, 1, 1, 1)

. Each panel represents a different choice of a Harr-random unitary matrix. For each choice of unitary matrix, 10,000 samples are taken. For this quantity of samples, the maximum standard deviation of the number of samples is 50. There are cases in each panel for which the number of events sampled deviate between the two cases by 5 to 10 standard deviations.

View in Article | Download Full Size | PDF

Fig. 3. Simulation of boson sampling and mean-field sampling with the input state

S = (0, 1, 1, 0)

. We chose four random matrices by the Harr measure and sampled them 10,000 times for each matrix. The same expected variation as in Fig. 2 applies to these data.

View in Article | Download Full Size | PDF

Fig. 4. Simulation of boson sampling, classical sampling, partially distinguishable boson sampling, and mean-field sampling with the input state

S = (1, 1, 1)

. Four randomly chosen matrices are displayed, with 10,000 samples for each case. We chose the coefficients for the Fock basis state in Eq. (16) to be identical, i.e.,

\frac{1}{\sqrt{6}}

, as there are 6 Fock basis states in this example. In terms of two-photon interference, this is equivalent to having a 50% probability of finding that the input particles were indistinguishable.

View in Article | Download Full Size | PDF

Equations (16)

Equations on this page are rendered with MathJax. Learn more.

S_{B} = | s_{1}, s_{2}, \dots, s_{N} ⟩ = \prod_{j = 1}^{N} \frac{{({\hat{a}}_{j}^{†})}^{s_{j}}}{\sqrt{s_{j}!}} | 0 ⟩ = \frac{{(a_{1}^{†})}^{s_{1}} {(a_{2}^{†})}^{s_{2}} \dots {(a_{N}^{†})}^{s_{N}}}{\sqrt{s_{1}! s_{2}! \dots s_{N}!}} | 0 ⟩,

\hat{S} {\hat{a}}_{j}^{†} {\hat{S}}^{†} = \sum_{k = 1}^{N} Λ_{k, j} {\hat{a}}_{k}^{†},

P_{B} (T_{B}; S_{B}, Λ) = \frac{{| Permanent (A) |}^{2}}{\prod_{i = 1}^{N} s_{i}! t_{i}!},

P_{D} (T_{D}; S_{D}, Λ) = \frac{Permanent (Ω)}{\prod_{i = 1}^{N} \sqrt{s_{i}! t_{i}!}},

| ψ ⟩ = \frac{1}{\sqrt{n}} \sum_{p = 1}^{n} e^{i θ_{p}} {\hat{a}}_{j_{p}}^{†} | 0 ⟩,

\hat{S} | ψ ⟩ = \frac{1}{\sqrt{n}} \sum_{p = 1}^{n} e^{i θ_{p}} \hat{S} {\hat{a}}_{j_{p}}^{†} {\hat{S}}^{†} | 0 ⟩ = \frac{1}{\sqrt{n}} \sum_{k = 1}^{N} \sum_{p = 1}^{n} e^{i θ_{p}} Λ_{k, j_{p}} {\hat{a}}_{j_{p}}^{†} | 0 ⟩ .

p_{k} = \frac{1}{n} {| \sum_{p = 1}^{n} e^{i θ_{p}} Λ_{k, j_{p}} |}^{2} .

P_{M f} (T_{M f}; S_{M f}, Λ) = (\begin{matrix} n \\ t_{1} \end{matrix}) (\begin{matrix} n - t_{1} \\ t_{2} \end{matrix}) \dots (\begin{matrix} t_{N} \\ t_{N} \end{matrix}) p_{1}^{t_{1}} p_{2}^{t_{2}} \dots p_{N}^{t_{N}} = \frac{n!}{n^{n} \prod_{l = 1}^{N} t_{l}!} \prod_{k = 1}^{N} {| \sum_{p = 1}^{n} e^{i θ_{p}} Λ_{k, j_{p}} |}^{2 t_{k}} = \frac{n!}{n^{n} \prod_{l = 1}^{N} t_{l}!} \prod_{q = 1}^{n} {| \sum_{p = 1}^{n} e^{i θ_{p}} Λ_{k_{q}, j_{p}} |}^{2} .

{\tilde{P}}_{M f} (T_{M f}; S_{M f}, Λ) = \int_{0}^{2 π} \frac{d θ_{1}}{2 π} \dots \int_{0}^{2 π} \frac{d θ_{n}}{2 π} P_{M f} (T_{M f}; S_{M f}, Λ) = \frac{n!}{n^{n} \prod_{l = 1}^{N} t_{l}!} \prod_{q = 1}^{n} \sum_{p = 1}^{n} {| Λ_{k_{q}, j_{p}} |}^{2} .

\hat{S} S_{C s} = \exp (- \frac{1}{2} \sum_{j = 1}^{N} {| α_{j} |}^{2}) \exp (\sum_{k = 1}^{N} \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} {\hat{a}}_{k}^{†}) | 0 ⟩ .

\hat{S} S_{C s} = \otimes_{k = 1}^{N} \exp (- \frac{1}{2} {| \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} |}^{2}) \exp (\sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} {\hat{a}}_{k}^{†}) | 0 ⟩ = \otimes_{k = 1}^{N} \exp (- \frac{1}{2} {| \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} |}^{2}) \sum_{n_{k} = 0}^{\infty} \frac{{(\sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j})}^{n_{k}}}{\sqrt{n_{k}!}} | n_{k} ⟩ .

P_{C s} (T_{C s}; S_{C s}, Λ) = \exp (- \sum_{k = 1}^{N} {| \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} |}^{2}) \prod_{k = 1}^{N} \frac{{| \sum_{j = 1}^{N} e^{i χ_{j}} α_{j} Λ_{k, j} |}^{2 t_{k}}}{t_{k}!} .

{\tilde{P}}_{C s} (T_{C s}; S_{C s}, Λ) = \exp (- \sum_{k, j = 1}^{N} {| α_{j} Λ_{k, j} |}^{2}) \prod_{k = 1}^{N} \frac{{(\sum_{j = 1}^{N} {| α_{j} Λ_{k, j} |}^{2})}^{t_{k}}}{t_{k}!} .

{\tilde{P}}_{M f} (T_{M f}; S_{T}, Λ) = \frac{n!}{n^{n} \prod_{k = 1}^{N} t_{k}!} .

{\hat{a}}_{j_{r}}^{†} = \sum_{k = 1}^{j_{r}} C_{r, k} {\hat{a}}_{j_{r}, t_{k}}^{†},

| S_{B} ⟩ = {\hat{a}}_{j_{1}, t_{1}}^{†} \sum_{k_{2} = 1}^{2} \sum_{k_{3} = 1}^{3} \dots \sum_{k_{n} = 1}^{n} \prod_{r = 2}^{n} C_{r, k_{r}} {\hat{a}}_{j_{r}, t_{k_{r}}}^{†} | 0 ⟩ .

Abstract

1. INTRODUCTION

2. SAMPLING MODELS

A. Boson Sampling

B. Classical Sampling

C. Mean-Field Sampling

D. Coherent-State Sampling

3. CERTIFICATION PROTOCOL

A. Certification via the N Photon Single-Photon Input State

B. Robustness for the Partially Distinguishable Boson Sampling

4. CONCLUSIONS

Funding

REFERENCES

Cited By

Figures (4)

Equations (16)

Journal of the Optical Society of America B

A. Certification via the $N$ Photon Single-Photon Input State