Decision and function problems based on boson sampling
This work explores new cryptographic applications for boson sampling, but it is incremental as it builds on existing theoretical frameworks without demonstrating practical implementations.
The paper investigates whether boson sampling, a problem intractable for classical computers, can be used to create computationally hard decision and function problems with potential cryptographic applications, and estimates that the required sample sizes for solving these problems with passive linear interferometers are independent of Hilbert space size.
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.