arXiv:1508.04099 · Laser Physics Letters

Permanents, bosons and linear optics

Alexander Yu. Vlasov

Published Sep 18, 2017• 2 citations

Abstract

Abstract The particular complexity of linear quantum optical networks has received certain deserved attention recently due to the possible implications for the theory of quantum computation. Two relevant boson models are discussed in the presented work. The symmetric product of the Hilbert spaces produces a rather abstract model; the second one is obtained by quantization of the harmonic oscillator. In contrast to the considered bosonic processes, the so-called ‘fermionic linear optics’ is effectively simulated on a classical computer. The comparison of the bosonic and fermionic case clarifies the controversy, and the more elaborate oscillator model provides a deeper analogy.

DOI: 10.1088/1612-202x/aa7d90

Related papers

Inefficiency of classically simulating linear optical quantum computing with Fock-state inputs

Bryan Gard, Jonathan P. Olson, Robert M. Cross +3 more

Aaronson and Arkhipov recently used computational complexity theory to argue that classical computers very likely cannot efficiently simulate linear, multimode, quantum-optical interferometers with arbitrary Fock-state inputs [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)]. Here we present an elementary argument that utilizes only techniques from quantum optics. We explicitly construct the Hilbert space for such an interferometer and show that its dimension scales exponentially with all the physical resources. We also show in a simple example just how the Schr\"odinger and Heisenberg pictures of quantum theory, while mathematically equivalent, are not in general computationally equivalent. Finally, we conclude our argument by comparing the symmetry requirements of multiparticle bosonic to fermionic interferometers and, using simple physical reasoning, connect the nonsimulatability of the bosonic device to the complexity of computing the permanent of a large matrix.

arXiv:1304.4206Physical Review AFeb 18, 201422 citations

The Computational Complexity of Linear Optics

Scott Aaronson, Arkhipov, Alex

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation. Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the "Permanent-of-Gaussians Conjecture", which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the "Permanent Anti-Concentration Conjecture", which says that |Per(A)|>=sqrt(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.

arXiv:1011.3245Electronic colloquium on computational complexityJan 25, 201020 citations

Permanents in linear optical networks

Stefan Scheel

We develop an abstract look at linear optical networks from the viewpoint of combinatorics and permanents. In particular we show that calculation of matrix elements of unitarily transformed photonic multi-mode states is intimately linked to the computation of permanents. An implication of this remarkable fact is that all calculations that are based on evaluating matrix elements are generically computationally hard. Moreover, quantum mechanics provides simpler derivations of certain matrix analysis results which we exemplify by showing that the permanent of any unitary matrix takes its values across the unit disk in the complex plane.

arXiv:quant-ph/0406127Jun 18, 200494 citations

Fermionic Linear Optics and Matchgates

Emanuel H. Knill

Fermionic linear optics is efficiently classically simulatable. Here it is shown that the set of states achievable with fermionic linear optics and particle measurements is the closure of a low dimensional Lie group. The weakness of fermionic linear optics and measurements can therefore be explained and contrasted with the strength of bosonic linear optics with particle measurements. An analysis of fermionic linear optics is used to show that the two-qubit matchgates and the simulatable matchcircuits introduced by Valiant generate a monoid of extended fermionic linear optics operators. A useful interpretation of efficient classical simulations such as this one is as a simulation of a model of non-deterministic quantum computation. Problem areas for future investigations are suggested.

arXiv:quant-ph/0108033Aug 7, 200173 citations

Majorization and the time complexity of linear optical networks

Seungbeom Chin, Joonsuk Huh

Abstract This work shows that the majorization of photon distributions is related to the runtime of classically simulating multimode passive linear optics, which explains one aspect of the boson sampling hardness. A Shur-concave quantity which we name the Boltzmann entropy of elementary quantum complexity ( ) is introduced to present some quantitative analysis of the relation between the majorization and the classical runtime for simulating linear optics. We compare with two quantities that are important criteria for understanding the computational cost of the photon scattering process, (the runtime for the classical simulation of linear optics) and (the additive error bound for an approximated amplitude estimator). First, for all the known algorithms for computing the permanents of matrices with repeated rows and columns, the runtime becomes shorter as the input and output distribution vectors are more majorized. Second, the error bound decreases as the majorization difference of input and output states increases. We expect that our current results would help in understanding the feature of linear optical networks from the perspective of quantum computation.

arXiv:1710.05551Journal of Physics A Mathematical and TheoreticalMay 17, 20198 citations

Quantum Photonics Beyond Conventional Computing

Jeremy L. O’Brien

Abstract : This project builds toward a simplified quantum information processing device which, though simpler than a universal quantum computer, uses far fewer resources and can still outperform any classical device for a particular specific task. Using the evolution of photons through linear optical networks for computation, we introduce the Boson Sampling model of linear optical quantum computing, realizing the first universally reconfigurable linear optical circuit, and demonstrate how the device can perform quantum simulations of the evolution of vibrational wave-packets in molecules, suggesting that such an approach could yield the first meaningful quantum simulations which are not possible with classical computation.

Jul 10, 20150 citations