US-12619677-B2 - Binary optimization using shallow boson sampling

Abstract

The present disclosure describes a system with a boson sampler that generates an output bosonic state by performing a transformation on an input bosonic state and produces measurement outcomes indicating the presence or absence of bosons in output modes. A controller of the system receives these measurement outcomes, generates binary sequences based on the presence or absence of bosons, and determines a solution to a binary optimization problem.

Inventors

• Hugo Wallner
• Kamil BRADLER

Assignees

• ORCA Computing Limited

Dates

Publication Date

20260505

Application Date

20220211

Priority Date

20211028

Claims (19)

1. 1 . A system comprising: a photonic boson sampler comprising: a set of one or more light sources configured to generate an input state comprising a plurality of input modes; a reconfigurable shallow interferometer comprising one or more configurable parameters, the reconfigurable shallow interferometer configured to generate an output state comprising a plurality of output modes by performing a transformation on the input state, wherein the transformation is dependent on one or more parameter values of the one or more configurable parameters; and an arrangement of one or more photon detectors configured to produce a measurement outcome indicative of a presence or absence of photons in the plurality of output modes of the output state; and a controller configured to: receive measurement outcomes from the photonic boson sampler, the measurement outcomes generated by the photonic boson sampler being operated multiple times; generate binary sequences based on the measurement outcomes, wherein values of the binary sequences are based on the presence or absence of photons in output modes of output states generated by the photonic boson sampler; and determine a solution to a binary optimization problem based at least in part on the generated binary sequences.
2. 2 . The system of claim 1 , wherein to generate the binary sequences, the controller is configured to: map a first measurement outcome to a first binary sequence, wherein each element of the first binary sequence corresponds to an output mode of a first output state and has a value based on whether one or more photons were present or absent in the output mode.
3. 3 . The system of claim 1 , wherein: the input state of the photonic boson sampler comprises M input modes, wherein M is an integer greater than or equal to two; and the reconfigurable shallow interferometer comprises fewer than M(M−1)/2 multimodal operations.
4. 4 . The system of claim 1 , wherein the plurality of input modes of the input state are a plurality of temporal modes.
5. 5 . The system of claim 4 , wherein the reconfigurable shallow interferometer comprises one or more temporal mode coupling devices, wherein a temporal mode coupling device comprises a reconfigurable beam splitter and a delay line, the delay line configured to connect one input port of the reconfigurable beam splitter with one output port of the reconfigurable beam splitter.
6. 6 . The system of claim 5 , wherein the reconfigurable beam splitter is capable of coupling modes with a reconfigurable reflection coefficient.
7. 7 . The system of claim 5 , wherein the reconfigurable beam splitter comprises a Mach-Zehnder interferometer.
8. 8 . The system of claim 4 , wherein the reconfigurable shallow interferometer comprises one or more temporal mode coupling devices, wherein a temporal mode coupling device comprises a quantum memory.
9. 9 . The system of claim 1 , wherein the plurality of input modes of the input state are a plurality of spatial modes.
10. 10 . The system of claim 9 , wherein the reconfigurable shallow interferometer comprises a spatial interferometer, the spatial interferometer comprising: M input ports for inputting M input modes of the input state into the spatial interferometer; M output ports for outputting M output modes of the output state from the spatial interferometer; and a plurality of waveguides arranged to pass through the spatial interferometer to connect the M input ports to the M output ports; wherein the plurality of waveguides are arranged to provide a plurality of coupling locations between pairs of the plurality of waveguides, wherein a reconfigurable beam splitter is arranged at each of the plurality of coupling locations such that at each coupling location of the plurality of coupling locations two modes of electromagnetic radiation carried by a pair of waveguides are capable of coupling with each other with a reconfigurable reflection coefficient.
11. 11 . The system of claim 10 , wherein the plurality of coupling locations are arranged such that at least one of the M input modes couples with each of the other M−1 input modes in the spatial interferometer.
12. 12 . The system of claim 10 , wherein the spatial interferometer comprises fewer than M(M−1)/2 coupling locations.
13. 13 . The system of claim 10 , wherein the reconfigurable shallow interferometer is comprised in an integrated photonic circuit.
14. 14 . The system of claim 1 , wherein: the controller is configured to receive the measurement outcomes and generate the binary sequences until a stopping condition is satisfied; and the controller is further configured to: until the stopping condition is satisfied, update the one or more parameter values of the one or more configurable parameters based on an objective function characteristic of the binary optimization problem; and when the stopping condition is satisfied, receive further measurement outcomes from the photonic boson sampler and generate further binary sequences based on the further measurement outcomes, wherein the controller is configured to determine the solution to the binary optimization problem based at least in part on the generated further binary sequences.
15. 15 . A method for using a photonic boson sampler to determine a solution to a binary optimization problem, wherein the photonic boson sampler is operable to: prepare an input state comprising a plurality of input modes; generate an output state comprising output modes by performing a transformation on the input state using a reconfigurable shallow interferometer; and produce measurement outcomes indicative of a presence or absence of photons in the output modes of the output state, the method comprising: receiving measurement outcomes from the photonic boson sampler, the measurement outcomes generated by the photonic boson sampler being operated multiple times; generating binary sequences based on the measurement outcomes, wherein values of the binary sequences are based on the presence or absence of photons in output modes of output states generated by the photonic boson sampler, and determining the solution to the binary optimization problem based at least in part on the generated binary sequences.
16. 16 . The method of claim 15 , wherein determining the solution to the binary optimization problem comprises: determining function values by evaluating an objective function using at least two of the generated binary sequences, the objective function characteristic of the binary optimization problem; and identifying, based at least in part on a comparison of the function values, a binary sequence as the solution to the binary optimization problem.
17. 17 . The method of claim 15 , wherein generating the binary sequences comprises: mapping a first measurement outcome to a first binary sequence, wherein each element of the first binary sequence corresponds to an output mode of a first output state and has a value based on whether one or more photons were present or absent in the output mode.
18. 18 . The method of claim 15 , wherein generating the binary sequences comprises: mapping a first measurement outcome to a first binary sequence according to a first mapping under which each element of the first binary sequence corresponds to an output mode of a first output state and has a first value if one or more photons were present in the output mode of the first output state and a second value if no photons were present in the output mode of the first output state; and mapping a second measurement outcome different than the first measurement outcome to a second binary sequence according to a second mapping under which each element of the second binary sequence corresponds to an output mode of a second output state and has the second value if one or more photons were present in the output mode of the second output state and the first value if no photons were present in the output mode of the second output state.
19. 19 . A non-transitory computer-readable storage medium comprising stored instructions that, when executed by a computing device, cause the computing device to perform operations, wherein the computing device is communicatively coupled to a photonic boson sampler operable to: prepare an input state comprising a plurality of input modes; generate an output state comprising output modes by performing a transformation on the input state using a reconfigurable shallow interferometer; and produce measurement outcomes indicative of a presence or absence of photons in the output modes of the output state, the operations including: receiving measurement outcomes from the photonic boson sampler, the measurement outcomes generated by the photonic boson sampler being operated multiple times; generating binary sequences based on the measurement outcomes, wherein values of the binary sequences are based on the presence or absence of photons in output modes of output bosonic states generated by the photonic boson sampler; and determining a solution to a binary optimization problem based at least in part on the generated binary sequences.

Description

CROSS-REFERENCE TO RELATED APPLICATION This application claims priority to United Kingdom Application No. GB2116924.8, “Binary Optimization Using Shallow Boson Sampler,” filed on Nov. 24, 2021 and claims priority to United Kingdom Application No. GB2115490.1, “Binary Optimization with Boson Sampling,” filed on Oct. 28, 2021, each of 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 reducing (e.g., minimizing) or increasing (e.g., 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 known 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. QUBO is known to be 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 is provided. 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 indicates the presence or absence of bosons in measured output modes of the multimodal output 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 stopping condition is satisfied. The controller is further operable to (v) after the stopping condition is satisfied, cause the boson sampler to be operated with the finalised set of parameter values. The controller is further operable 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 whether one or more bosons were present or absent 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 at least in part 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 the presence or absence 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, the boson sampler does not require boson number resolving detectors as only the presence or absence of bosons need be determined, and this means that less