Decision and function problems based on boson sampling
arXiv:1607.02987 · doi:10.1103/PhysRevA.94.012315
Abstract
Boson sampling is a mathematical problem that is strongly believed to be intractable for classical computers, whereas passive linear interferometers can produce samples efficiently. So far, the problem remains a computational curiosity, and the possible usefulness of boson-sampling devices is mainly limited to the proof of quantum supremacy. The purpose of this work is to investigate whether boson sampling can be used as a resource of decision and function problems that are computationally hard, and may thus have cryptographic applications. After the definition of a rather general theoretical framework for the design of such problems, we discuss their solution by means of a brute-force numerical approach, as well as by means of non-boson samplers. Moreover, we estimate the sample sizes required for their solution by passive linear interferometers, and it is shown that they are independent of the size of the Hilbert space.
Close to the version published in PRA
References in corpus (10)
- Photonic Boson Sampling in a Tunable Circuit
- Boson Sampling for Molecular Vibronic Spectra
- Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
- Partial indistinguishability theory for multi-photon experiments in multiport devices
- What can quantum optics say about computational complexity theory?
- Many-particle interference beyond many-boson and many-fermion statistics
- Universality of Generalized Bunching and Efficient Assessment of Boson Sampling
- Tight bound on trace distance between a realistic device with partially indistinguishable bosons and the ideal Boson Sampling
- Optical quantum computing with photons of arbitrarily low fidelity and purity
- Certification of Boson Sampling Devices with Coarse-Grained Measurements
Cited by in corpus (12)
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- Perceval: A Software Platform for Discrete Variable Photonic Quantum Computing
- Continuous-variable quantum authentication of physical unclonable keys
- Cryptographic One-way Function Based on Boson Sampling
- Proof-of-work consensus by quantum sampling
- Efficient validation of Boson Sampling from binned photon-number distributions
- BosonSampling.jl: A Julia package for quantum multi-photon interferometry
- Efficiently simulating the work distribution of multiple identical bosons with boson sampling
- Computational indistinguishability and boson sampling
- Generalized Interference of Fermions and Bosons
- Physical Unclonable Functions with Boson Sampling
- Global estimates of errors in quantum computation by the Feynman-Vernon formalism