Quantum computation for optimization in exchange systems

1. A computer-implemented method comprising:

receiving data representing an exchange problem;

determining, from the received data, an integer programming formulation of the exchange problem, the integer programming formulation of the exchange problem comprising: i) an objective function to be maximized, ii) one or more constraints comprising equality and inequality constraints;

mapping the integer programming formulation of the exchange problem to a quadratic unconstrained binary optimization (QUBO) formulation of the exchange problem, comprising:

mapping the objective function to be maximized to a QUBO objective function to be minimized:

determining a penalty term, comprising, for each equality constraint:

representing the constraint as an equation equaling zero when the constraint is satisfied and equaling a strictly positive value when the constraint is not satisfied;

multiplying the equation by a weight to generate a corresponding partial-penalty term; and

including the generated partial-penalty terms in the penalty term; and

adding the penalty term to the QUBO objective function to be minimized;

obtaining data representing a solution to the exchange problem from a quantum computing resource; and

initiating an action based on the obtained data representing a solution to the exchange problem.

2. The method of claim 1 , further comprising:

for each inequality constraint:

formulating the inequality constraint as an equality constraint comprising slack variables, wherein each slack variable is a binary variable; and

determining the penalty term using the equality constraint comprising slack variables.

3. The method of claim 1 , wherein when the quantum computing resource comprises a quantum annealing computer, optionally wherein the solution to the exchange problem is computed using quantum adiabatic computation.

4. The method of claim 1 , wherein when the quantum computing resource comprises a gate-based universal quantum computer, optionally wherein the solution to the exchange problem is computed using a Quantum Approximate Optimization Approach or other quantum-classical hybrid variational algorithm.

5. The method of claim 1 , further comprising performing classical post-processing of the data representing a solution to the exchange problem obtained from the quantum computing resource.

6. The method of claim 1 , wherein initiating an action based on the obtained data representing a solution to the exchange problem comprises exchanging resources or services based on the solution to the exchange problem.

7. The method of claim 1 , wherein the received data comprises data representing:

exchange problem participants, wherein each participant offers resources or services in exchange for other resources or services without using a medium of exchange;

constraints on exchanges between exchange problem participants; and

the exchange problem.

8. The method of claim 7 , wherein the exchange problem comprises a kidney exchange problem.

9. The method of claim 8 , wherein the exchange problem participants comprise incompatible donor-recipient pairs, wherein each incompatible donor-recipient pair comprises (i) a donor willing to donate a kidney, and (ii) a patient in need of a donor kidney of a different type to that offered by the donor.

10. The method of claim 8 , wherein constraints on exchanges between exchange problem participants comprise:

a first constraint that ensures no kidney is donated more than once;

a second constraint that ensures that a donor of an incompatible donor-recipient pair donates a kidney only if a patient in the incompatible donor-recipient pair receives a kidney from another donor.

11. The method of claim 8 , further comprising:

modelling the kidney exchange problem as a graph of vertices and directed weighted edges, wherein

vertices represent incompatible donor-recipient pairs,

edges represent compatible donor-recipient pairs; and

edge weights represent a medical benefit of a compatible donor-recipient pair; and

determining one or more disjoint cycles of donor-recipient pairs that increases overall medical benefits of associated kidney transplants.

12. The method of claim 11 , wherein a number of donor-recipient pairs in each of the one or more disjoint cycles is below a predetermined threshold.

13. The method of claim 8 , wherein initiating an action based on the obtained data representing a solution to the exchange problem comprises transplanting multiple kidneys based on the solution to the exchange problem.

14. A system comprising:

a classical processor;

a quantum computing device in data communication with the classical processor;

wherein the classical processor and quantum computing device are configured to perform operations comprising:

receiving data representing an exchange problem;

determining, from the received data, an integer programming formulation of the exchange problem, the integer programming formulation of the exchange problem comprising: i) an objective function to be maximized, and ii) one or more constraints comprising equality and inequality constraints;

mapping the integer programming formulation of the exchange problem to a quadratic unconstrained binary optimization (QUBO) formulation of the exchange problem, comprising:

mapping the objective function to be maximized to a QUBO objective function to be minimized;

determining a penalty term, comprising, for each equality constraint:

representing the constraint as an equation equaling zero when the constraint is satisfied and equaling a strictly positive value when the constraint is not satisfied;

multiplying the equation by a weight to generate a corresponding partial-penalty term; and

including the generated partial-penalty terms in the penalty term; and

adding the penalty term to the QUBO objective function to be minimized;

obtaining data representing a solution to the exchange problem from a quantum computing resource; and

initiating an action based on the obtained data representing a solution to the exchange problem.

15. The system of claim 14 , further comprising:

for each inequality constraint:

formulating the inequality constraint as an equality constraint comprising slack variables, wherein each slack variable is a binary variable; and

determining the penalty term using the equality constraint comprising slack variables.

16. The system of claim 14 , wherein initiating an action based on the obtained data representing a solution to the exchange problem comprises exchanging resources or services based on the solution to the exchange problem.

17. The system of claim 14 , wherein the received data comprises data representing:

exchange problem participants, wherein each participant offers resources or services in exchange for other resources or services without using a medium of exchange;

constraints on exchanges between exchange problem participants; and

the exchange problem.

18. The system of claim 17 , wherein the exchange problem comprises a kidney exchange problem.