The computational complexity of linear optics
From MaRDI portal
Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Physical optics (78A10) Quantum computation (81P68)
Recommendations
- The computational complexity of linear optics
- A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
- scientific article; zbMATH DE number 7250159
- The classical complexity of boson sampling
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
Cites work
Cited in
(70)- The classical complexity of boson sampling
- The complexity of approximating complex-valued Ising and Tutte partition functions
- Microwave photonics with superconducting quantum circuits
- Unified quantum no-go theorems and transforming of quantum pure states in a restricted set
- Roughness as classicality indicator of a quantum state
- On the permanent of a random symmetric matrix
- Simulating macroscopic quantum correlations in linear networks
- Quantum path computing: computing architecture with propagation paths in multiple plane diffraction of classical sources of fermion and boson particles
- Performance of the quantum maxent estimation in the presence of physical symmetries
- Cryptographic one-way function based on boson sampling
- Efficient computation of permanents, with applications to boson sampling and random matrices
- Establishing simple relationship between eigenvector and matrix elements
- Classically simulating quantum circuits with local depolarizing noise
- A little bit of classical magic to achieve (super-)quantum speedup
- The equivalence of sampling and searching
- Fermionic linear optics revisited
- Near invariance of the hypercube
- Parameterizing density operators with arbitrary symmetries to gain advantage in quantum state estimation
- Optical Implementation of Linear Canonical Transforms
- Computing the permanent of (some) complex matrices
- A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
- On immanant functions related to Weyl groups of \(A_{n}\)
- Testing permanent oracles -- revisited
- Algorithms for \(\mathrm{SU}(n)\) boson realizations and \(\mathcal{D}\)-functions
- scientific article; zbMATH DE number 1738670 (Why is no real title available?)
- How to Verify a Quantum Computation
- Quantum de Moivre–Laplace theorem for noninteracting indistinguishable particles in random networks
- The classification of reversible bit operations
- Approximating permanents and hafnians
- Classical simulation of disspative fermionic linear optics
- The computational complexity of ball permutations
- On the classical complexity of sampling from quantum interference of indistinguishable bosons
- scientific article; zbMATH DE number 7453153 (Why is no real title available?)
- Majorization and the time complexity of linear optical networks
- scientific article; zbMATH DE number 7559454 (Why is no real title available?)
- Counting single-qubit Clifford equivalent graph states is \#\(\mathbb{P}\)-complete
- Spectral norm of a symmetric tensor and its computation
- The argument against quantum computers
- scientific article; zbMATH DE number 7250159 (Why is no real title available?)
- On the classical hardness of spoofing linear cross-entropy benchmarking
- Exact and efficient simulation of concordant computation
- Boson-sampling with non-interacting fermions
- On the power of quantum Fourier sampling
- Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons
- The computational complexity of linear optics
- Statistical benchmark for bosonsampling
- Towards quantum supremacy with lossy scattershot boson sampling
- Unitary matrix decompositions for optimal and modular linear optics architectures
- Algorithmic foundations for the diffraction limit
- \texttt{QOptCraft}: a python package for the design and study of linear optical quantum systems
- Approximate orthogonality of permutation operators, with application to quantum information
- Many-particle interference in a two-component bosonic Josephson junction: an all-optical simulation
- A polynomial-time classical algorithm for noisy random circuit sampling
- Families of bosonic suppression laws beyond the permutation symmetry principle
- Quantifying non-stabilizerness via information scrambling
- Integrating products of quadratic forms
- Photonic quantum information processing using the frequency continuous variable of single photons
- Permanent of bipartite graphs in terms of determinants
- Permanental ideals of symmetric matrices
- Fair selection of clearing schemes for kidney exchange markets
- A qubit, a coin, and an advice string walk into a relational problem
- Quantum algorithms for stochastic differential equations: a Schrödingerisation approach
- Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target
- Eigenvalues of product of Ginibre ensembles and their inverses and that of truncated Haar unitary matrices and their inverses
- New inequalities for permanents and hafnians and some generalizations
- Hong-Ou-Mandel interference on a lattice: symmetries and interactions
- Global estimates of errors in quantum computation by the Feynman-Vernon formalism
- Combinatorics. Abstracts from the workshop held January 4--9, 2026
- Uniformity testing when you have the source code
- Equalities and inequalities from entanglement, loss, and beam splitters
This page was built for publication: The computational complexity of linear optics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191572)
