Majorization and the time complexity of linear optical networks
arXiv:1710.05551 · doi:10.1088/1751-8121/ab1cc7
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 \emph{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 comment12 pages, 4 figures; (v3) Accepted version (Journal of Physics A)
References in corpus (32)
- Review article: Linear optical quantum computing
- Quantum Coherence as a Resource
- Universal Linear Optics
- Conditions for a class of entanglement transformations
- Photonic Boson Sampling in a Tunable Circuit
- Entanglement by a beam splitter: nonclassicality as a prerequisite for entanglement
- Gaussian Boson Sampling
- Integrated photonic quantum gates for polarization qubits
- Generating, manipulating and measuring entanglement and mixture with a reconfigurable photonic circuit
- Conditions for coherence transformations under incoherent operations
- A theorem for the beam splitter entangler
- Extracting entanglement from identical particles
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
- Family of Concurrence Monotones and its Applications
- Stringent and efficient assessment of Boson-Sampling devices
- Enhancing quantum transport in a photonic network using controllable decoherence
- Efficient algorithm for boson sampling with partially distinguishable photons
- Generalized multi-photon quantum interference
- Partial indistinguishability theory for multi-photon experiments in multiport devices
- Interference of Identical Particles from Entanglement to Boson-Sampling
- What can quantum optics say about computational complexity theory?
- A Linear-Optical Proof that the Permanent is #P-Hard
- Multiphoton entanglement through a Bell multiport beam splitter
- Mixing nonclassical pure states in a linear-optical network almost always generates modal entanglement
- The Majorization Arrow in Quantum Algorithm Design
- Multiparticle correlations in mesoscopic scattering: boson sampling, birthday paradox, and Hong-Ou-Mandel profiles
- Generalized concurrence in boson sampling
- Experimental Demonstration of Robust Bidirectional Quantum Optical Communications
- Generating entanglement with linear optics
- Generalized Coherence Concurrence and Path distinguishability
- Systematic Analysis of Majorization in Quantum Algorithms
Cited by in corpus (4)
- Entangling Bosons through Particle Indistinguishability and Spatial Overlap
- The principle of majorization: application to random quantum circuits
- Shortcut to Multipartite Entanglement Generation: A Graph Approach to Boson Subtractions
- Partial Distinguishability as a Coherence Resource in Boson Sampling