Generalized concurrence in boson sampling

Abstract

A fundamental question in linear optical quantum computing is to understand the origin of the quantum supremacy in the physical system. It is found that the multimode linear optical transition amplitudes are calculated through the permanents of transition operator matrices, which is a hard problem for classical simulations (boson sampling problem). We can understand this problem by considering a quantum measure that directly determines the runtime for computing the transition amplitudes. In this paper, we suggest a quantum measure named "Fock state concurrence sum" $C_S$, which is the summation over all the members of "the generalized Fock state concurrence" (a measure analogous to the generalized concurrences of entanglement and coherence). By introducing generalized algorithms for computing the transition amplitudes of the Fock state boson sampling with an arbitrary number of photons per mode, we show that the minimal classical runtime for all the known algorithms directly depends on $C_S$. Therefore, we can state that \emph{the Fock state concurrence sum $C_S$ behaves as a collective measure that controls the computational complexity of Fock state BS}. We expect that our observation on the role of the Fock state concurrence in the generalized algorithm for permanents would provide a unified viewpoint to interpret the quantum computing power of linear optics.

11 pages, 1 figure

References in corpus (14)

• Quantum Coherence as a Resource
• Gaussian Boson Sampling
• Universal resources for measurement-based quantum computation
• Coherence depletion in the Grover quantum search algorithm
• A resource theory of superposition
• Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
• Universal quantum computation with little entanglement
• What can quantum optics say about computational complexity theory?
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• Vibronic Boson Sampling: Generalized Gaussian Boson Sampling for Molecular Vibronic Spectra at Finite Temperature
• Coherence number as a discrete quantum resource
• Quantifying entanglement of maximal dimension in bipartite mixed states
• Generalized Coherence Concurrence and Path distinguishability
• Entanglement monotones and transformations of symmetric bipartite states

Cited by in corpus (14)

• A detailed study of Gaussian Boson Sampling
• Computational advantage of quantum random sampling
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Classical simulation of linear optics subject to nonuniform losses
• Quantum-inspired permanent identities
• Quantum supremacy of the many-body fluctuations in the occupations of the excited particle states in a Bose-Einstein-condensed gas
• Piquasso: A Photonic Quantum Computer Simulation Software Platform
• Majorization and the time complexity of linear optical networks
• Partial Distinguishability as a Coherence Resource in Boson Sampling
• Rényi entanglement entropy after a quantum quench starting from insulating states in a free boson system
• Entanglement in the full state vector of boson sampling
• High performance Boson Sampling simulation via data-flow engines
• Quantum estimation bound of Gaussian matrix permanent
• Classical modelling of a bosonic sampler with photon collisions