Mapping optimization problems onto boson sampling circuits

Certain properties and applications of shallow bosonic circuits

This arXiv preprint comes from ORCA Computing, an Oxford University spin-off company pursuing fibre optic-based quantum computing. In brief, the fibre optic platform uses trains of time-delayed single photon pulses and number-resolved photon detection.

The authors consider how variational quantum eigensolvers, an immensely popular class of algorithms for near-term qubit-based systems such as superconducting quantum processors, may be mapped to shallow linear interferometers employed for boson sampling experiments. Their idea is:

1. Boson sampling circuits sample from a distribution integer strings (n1,n2,...nM), where ni corresponds to n photons detected in mode i.

2. Taking the parity of the output maps this to a distribution of bitstrings (b1,...,bM), which can be interpreted as a measurement of a qubit-based system in the computational basis.

3. Under certain constraints this parity mapping allows one to sample from a complete basis of the qubit Hilbert space and thereby measure cost functions of binary optimization problems such as QUBO.

4. Output observables obey the parameter shift rule, making gradient-based minimization of the cost function to solve the optimization problem practical.

I think studies such as this on mappings between qubit-based and bosonic NISQ devices are important. While a few general-purpose optimization algorithms for qubit systems have been developed, proposed applications of NISQ bosonic circuits remain largely limited to "hardware native" schemes, i.e. simulation of properties of bosonic Hamiltonians such as molecular vibration spectra. This work provides a general scheme by which one might solve more general optimization problems using boson sampling devices, making them much more valuable for end-users.

However, two caveats I can see:

1. The QAOA algorithm is perhaps the most promising variational quantum algorithm, because it is a structured (problem-inspired) circuit with relatively few free parameters that need to be optimized, with some rigorous performance guarantees. While linear interferometers are described by a manageable number of free parameters, there is no guarantee that this kind of hardware-efficient circuit can always express the optimal solution to the optimization problem at hand.

2. The elephant in the room: Are the proposed circuits hard to simulate on a classical computer? While exact boson sampling is provably hard, hardness of the approximate sampling problem rests on the number of optical modes M being much larger than N^2, where N is the total number of input photons. In this limit there is a very low probability of detecting more than one photon in any output mode and the number resolved detection and parity map are not required. In their proof of concept simulations, however, the authors consider only the case M ~ N...