US-12619676-B2 - Binary optimization with boson sampling

US12619676B2US 12619676 B2US12619676 B2US 12619676B2US-12619676-B2

Abstract

A system may include a boson sampler configured to generate an output bosonic state by performing a parametrized unitary transformation on an input bosonic state. The system may include a controller coupled to the boson sampler. The controller may be configured to: (i) determine a set of one or more parameter values that defines the parametrized unitary transformation performed by the boson sampler, (ii) operate the boson sampler multiple times with the boson sampler tuned to the determined set of parameter values, (iii) record one or more responses of the boson sampler for the multiple operations (iv) generate binary sequences based on the responses, (v) calculate values of an objective function of a binary optimization problem, and (vi) determine a solution to the binary optimization problem based on the calculated values.

Inventors

Hugo Wallner
Kamil BRADLER

Assignees

ORCA Computing Limited

Dates

Publication Date: 20260505
Application Date: 20220124
Priority Date: 20211028

Claims (18)

1 . A system comprising: a boson sampler comprising: a set of one or more single photon sources, the set of one or more single photon sources configured to generate an input state comprising a plurality of input modes; a reconfigurable interferometer comprising one or more configurable parameters, the reconfigurable interferometer configured to generate an output state by performing a parametrized unitary transformation on the input state, wherein the parametrized unitary transformation is dependent on a set of one or more parameter values of the one or more configurable parameters; and an arrangement of one or more photon detectors, the arrangement of photon detectors configured to produce a measurement outcome indicative of a number of photons in output modes of the output state; and a controller coupled to the boson sampler, the controller configured to: (i) determine the set of one or more parameter values that defines, at least in part, the parametrized unitary transformation performed by the boson sampler, wherein determining the set of one or more parameter values is based on a binary optimization problem; (ii) operate the boson sampler multiple times with the boson sampler tuned to the determined set of one or more parameter values; (iii) record one or more responses of the boson sampler for the multiple operations of the boson sampler, the one or more responses including measurement outcomes of the boson sampler; (iv) generate binary sequences based on the one or more responses, wherein to generate the binary sequences, the controller is further configured to map the measurement outcomes of the boson sampler to the binary sequences, wherein each element of one of the binary sequences corresponds to one of the output modes of the output state and each element has a value based on a parity of a number of photons in the one of the output modes; (v) calculate values of an objective function of the binary optimization problem for at least two of the binary sequences; and (vi) determine a solution to the binary optimization problem based at least in part on the calculated values.
2 . The system of claim 1 , wherein the input state and the output state of the boson sampler each comprise M≥2 modes, and wherein the set of one or more parameter values for defining the parametrized unitary transformation of the boson sampler comprises fewer than M (M−1)/2 parameter values.
3 . The system of claim 1 , wherein the input state of the boson sampler comprises a plurality of input spatial modes.
4 . The system of claim 1 , wherein the input state of the boson sampler comprises a plurality of input temporal modes.
5 . The system of claim 1 , wherein the input state comprises M≥2 input modes, each input mode comprising a photon, and the output state comprises M output modes; wherein each binary sequence of the binary sequences has a number L>0 of elements that is fewer than M.
6 . The system of claim 5 , wherein the arrangement of one or more photodetectors of the boson sampler is configured to perform measurements on L of the M output modes of the output state.
7 . The system of claim 1 , wherein the input state comprises M≥2 input modes, each input mode comprising a photon; wherein the system further comprises a second boson sampler that, when operated, is configured to generate a second input state comprising M input modes, with M−1 input modes comprising a photon; and wherein the controller is further configured to perform steps (i) to (vi) using the second boson sampler.
8 . The system of claim 1 , wherein the reconfigurable interferometer comprises one or more reconfigurable beam splitters each with a configurable reflection coefficient.
9 . The system of claim 8 , wherein each reconfigurable beam splitter comprises a Mach-Zehnder interferometer.
10 . The system of claim 8 , wherein the reconfigurable interferometer is comprised in an integrated photonic circuit.
11 . The system of claim 1 , wherein the input state and the output state of the boson sampler each comprise M≥2 modes, and wherein the reconfigurable interferometer comprises fewer than M configurable parameters.
12 . A method comprising: determining a set of one or more parameter values that defines, at least in part, a parametrized unitary transformation of a boson sampler, wherein determining the set of one or more parameter values is based on a cost function associated with a binary optimization problem, wherein the boson sampler comprises: a set of one or more single photon sources, the set of one or more single photon sources configured to generate an input state comprising a plurality of input modes; a reconfigurable interferometer comprising one or more configurable parameters, the reconfigurable interferometer configured to generate an output state by performing the parametrized unitary transformation on the input state, wherein the parametrized unitary transformation is dependent on the set of one or more parameter values of the one or more configurable parameters; and an arrangement of one or more photon detectors, the arrangement of photon detectors configured to produce a measurement outcome indicative of a number of photons in output modes of the output state; generating instructions to operate the boson sampler multiple times with the boson sampler tuned to the determined set of one or more parameter values; recording one or more responses of the boson sampler for the multiple operations of the boson sampler, the one or more responses indicating measurement outcomes of the boson sampler; generating binary sequences based on the one or more responses, wherein generating the binary sequences comprises mapping the measurement outcomes of the boson sampler to the binary sequences, wherein each element of one of the binary sequences corresponds to one of the output modes of the output state and each element has a value based on a parity of a number of photons in the one of the output modes; calculating values of an objective function of the binary optimization problem for at least two of the binary sequences; and determining a solution to the binary optimization problem based at least on the calculated values.
13 . The method of claim 12 , wherein one of the measurement outcomes indicates a measurement of a number of photons in one of the output modes of the output state.
14 . The method of claim 12 , wherein one of the measurement outcomes indicates a measurement of a parity of a number of photons in one of the output modes of the output state.
15 . The method of claim 12 , wherein determining the set of one or more parameter values comprises: determining initial parameters values for the set of one or more parameter values; generating instructions to operate the boson sampler tuned to different parameter values; receiving measurement outcomes of output states of the boson sampler; estimating a gradient of the cost function with respect to a parameter associated with the set of one or more parameter values, wherein the cost function is calculated based on the received measurement outcomes; and determining updated values for the set of one or more parameter values based on the estimated gradient of the cost function.
16 . The method of claim 12 , wherein the input state and the output state of the boson sampler each comprise M≥2 modes, and wherein the reconfigurable interferometer comprises fewer than M configurable parameters.
17 . A non-transitory computer-readable storage medium comprising stored instructions that, when executed by a computing device, cause the computing device to perform operations including: determining a set of one or more parameter values that defines, at least in part, a parametrized unitary transformation of a boson sampler, wherein determining the set of one or more parameter values is based on a cost function associated with a binary optimization problem, wherein the boson sampler comprises: a set of one or more single photon sources, the set of one or more single photon sources configured to generate an input state comprising a plurality of input modes; a reconfigurable interferometer comprising one or more configurable parameters, the reconfigurable interferometer configured to generate an output state by performing the parametrized unitary transformation on the input state, wherein the parametrized unitary transformation is dependent on the set of one or more parameter values of the one or more configurable parameters; and an arrangement of one or more photon detectors, the arrangement of photon detectors configured to produce a measurement outcome indicative of a number of photons in output modes of the output state; generating instructions to operate the boson sampler multiple times with the boson sampler tuned to the determined set of one or more parameter values; recording one or more responses of the boson sampler for the multiple operations of the boson sampler, the one or more responses indicating measurement outcomes of the boson sampler; generating binary sequences based on the one or more responses, wherein generating the binary sequences comprises mapping the measurement outcomes of the boson sampler to the binary sequences, wherein each element of one of the binary sequences corresponds to one of the output modes of the output state and each element has a value based on a parity of a number of photons in the one of the output modes; calculating values of an objective function of the binary optimization problem for at least two of the binary sequences; and determining a solution to the binary optimization problem based at least on the calculated values.
18 . The non-transitory computer-readable storage medium of claim 17 , wherein the input state and the output state of the boson sampler each comprise M≥2 modes, and wherein the reconfigurable interferometer comprises fewer than M configurable parameters.

Description

CROSS-REFERENCE TO RELATED APPLICATION This application claims priority to United Kingdom Application No. GB2115490.1, “Binary Optimization with Boson Sampling,” filed on Oct. 28, 2021, which is hereby incorporated by reference in its entirety. TECHNICAL FIELD The present disclosure relates to methods and systems for addressing binary optimization problems. More particularly, the present disclosure relates to methods and systems that utilize one or more boson sampling devices to determine solutions to binary optimization problems. BACKGROUND Binary optimization problems are a subclass of combinatorial optimization problems in which the variables are restricted to one of two values. A binary optimization problem can generally be stated as a problem of minimizing (or maximizing) an objective function of variables that can take one of two values, for example 0 or 1. One famous binary optimization problem is the Quadratic Unconstrained Binary Optimization (QUBO) problem, which is also referred to as the Unconstrained Binary Quadratic Programming (UBQP) problem. The task is to find a binary sequence b of length L that minimises the objective function bTQb where Q is an L×L symmetric matrix having real values. Many problems of real-world relevance can be cast into a QUBO form: for example, the travelling salesman problem in which one is given a list of destinations and distances therebetween and must devise the shortest route that visits each destination exactly once and returns to the starting point, may be cast as a QUBO problem. QUBO is an NP hard problem and so is intractable on a classical computer when the number L of binary variables is large. Techniques for solving binary optimization problems are desirable. SUMMARY Some embodiments relate to a system for determining a solution to a binary optimization problem. The system comprises a boson sampler and a controller. The boson sampler comprises a state generation module for generating an input multimodal bosonic state comprising a plurality of input modes. The boson sampler further comprises a linear bosonic circuit for performing a parametrised unitary transformation of the input multimodal bosonic state to an output multimodal bosonic state comprising a plurality of output modes. The boson sampler further comprises a state detection module for performing measurements on output modes of the output multimodal bosonic state to produce measurement outcomes, wherein each measurement outcome is based on the number of bosons in measured output modes of the output multimodal bosonic state. The controller is operable to (i) initialise a set of parameter values, the set of parameter values for defining the parametrised unitary transformation of the boson sampler. The controller is further operable to (ii) for at least one selected parameter, use the boson sampler to determine a gradient of a cost function with respect to that selected parameter. The controller is further operable to (iii) using the at least one determined gradient, update the set of parameter values. The controller is further operable to (iv) repeat (ii) and (iii) until a convergence criterion is satisfied. The controller is further operable to (v) after the convergence criterion is satisfied, cause the boson sampler to be operated with the converged set of parameter values. The controller is further configured to (vi) receive a response from the boson sampler, the response representative of an empirical probability distribution of measurement outcomes. The controller is further operable to (vii) map each distinct measurement outcome to a binary sequence of a plurality of binary sequences, wherein each element of a binary sequence corresponds to a measured output mode of the output multimodal bosonic state and has a value based on a parity of the number of bosons in that corresponding measured output mode. The controller is further operable to (viii) for at least two binary sequences to which a measurement outcome is mapped, evaluate an objective function using the binary sequence to determine a corresponding function value, the objective function characteristic of the binary optimization problem. The controller is further operable to (ix) identify, based on a comparison of the function values, a binary sequence as a solution to the binary optimization problem. Advantageously, the system described herein exploits both a classical computing resource and a quantum computing resource in the form of a boson sampler, to determine a solution to a binary optimization problem. By exploiting bosonic statistics and mapping measurement outcomes to binary sequences based on a parity of the number of bosons in an output mode, the system is able to handle even large binary optimization problems (those for which the candidate solutions have a large number of elements). Furthermore, by mapping measurement outcomes to binary sequences based on a parity of the number of bosons in an output mode, the boson sampler ma