Quantum computation for optimization in exchange systems

Abstract

Methods, systems, and apparatus for improving exchange systems. In one aspect, a method includes receiving data representing an exchange problem; determining, from the received data, an integer programming formulation of the exchange problem; mapping the integer programming formulation of the exchange problem to a quadratic unconstrained binary optimization (QUBO) formulation of the exchange problem; 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.

What is claimed is: 
     
         1 . (canceled) 
     
     
         2 . A computer-implemented method comprising:
 receiving data representing an exchange problem;   determining, from the received data, an integer programming formulation of the exchange problem, wherein the integer programming formulation of the exchange problem comprises one or more constraints;   mapping the integer programming formulation of the exchange problem to a quadratic unconstrained binary optimization (QUBO) formulation of the exchange problem, comprising:
 representing each constraint as a respective term equaling zero when the constraint is satisfied and equaling a strictly positive value when the constraint is not satisfied, and 
 including each term in the QUBO formulation of the exchange problem; 
   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.   
     
     
         3 . The method of  claim 2 , wherein the one or more constraints comprise at least one of i) equality, or ii) inequality constraints. 
     
     
         4 . The method of  claim 3 , wherein representing each constraint as a respective term equaling zero when the constraint is satisfied and equaling a strictly positive value when the constraint is not satisfied, and including each term in the QUBO formulation of the exchange problem comprises, 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 term in the QUBO formulation of the exchange problem.   
     
     
         5 . The method of  claim 3 , wherein representing each constraint as a respective term equaling zero when the constraint is satisfied and equaling a strictly positive value when the constraint is not satisfied, and including each term in the QUBO formulation of the exchange problem comprises, for each inequality constraint:
 formulating the inequality constraint as an equality constraint comprising slack variables, wherein each slack variable is a binary variable;   representing the equality constraint comprising slack variables 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 term in the QUBO formulation of the exchange problem.   
     
     
         6 . The method of  claim 2 , wherein the integer programming formulation of the exchange problem further comprises an objective function to be maximized. 
     
     
         7 . The method of  claim 6 , wherein mapping the integer programming formulation of the exchange problem to a QUBO formulation of the exchange problem comprises:
 mapping the objective function to be maximized to a QUBO objective function to be minimized; and   adding the terms equaling zero when the constraint is satisfied and equaling a strictly positive value when the constraint is not satisfied to the QUBO objective function to be minimized.   
     
     
         8 . The method of  claim 2 , wherein the quantum computing resource comprises a quantum annealing computer, and optionally wherein the solution to the exchange problem is computed using quantum adiabatic computation. 
     
     
         9 . The method of  claim 2 , wherein the quantum computing resource comprises a gate-based universal quantum computer, and optionally wherein the solution to the exchange problem is computed using a Quantum Approximate Optimization Approach or other quantum-classical hybrid variational algorithm. 
     
     
         10 . The method of  claim 2 , further comprising performing classical post-processing of the data representing a solution to the exchange problem obtained from the quantum computing resource to determine one or more actions to be taken based on the solution to the exchange problem. 
     
     
         11 . The method of  claim 2 , 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. 
     
     
         12 . The method of  claim 2 , wherein the exchange problem comprises a kidney exchange problem. 
     
     
         13 . The method of  claim 12 , 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 . The method of  claim 12 , 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.   
     
     
         15 . The method of  claim 14 , wherein the data representing the solution to the exchange problem comprises data representing one or more determined disjoint cycles of donor-recipient pairs that increases overall medical benefits of associated kidney transplants. 
     
     
         16 . The method of  claim 15 , wherein a number of donor-recipient pairs in each of the one or more determined disjoint cycles is below a predetermined threshold. 
     
     
         17 . The method of  claim 2 , 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 method of  claim 17 , wherein:
 the exchange problem comprises a kidney exchange problem,   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, and   constraints on exchanges between exchange problem participants comprise one or more of i) a first constraint that ensures no kidney is donated more than once, and ii) a second constraint that ensures that a donor of an incompatible donor-recipient pair donates a kidney only if the patient in the incompatible donor-recipient pair receives a kidney from another donor.   
     
     
         19 . 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, wherein the integer programming formulation of the exchange problem comprises one or more constraints; 
 mapping the integer programming formulation of the exchange problem to a quadratic unconstrained binary optimization (QUBO) formulation of the exchange problem, comprising:
 representing each constraint as a respective term equaling zero when the constraint is satisfied and equaling a strictly positive value when the constraint is not satisfied, and 
 including each term in the QUBO formulation of the exchange problem; 
 
 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. 
   
     
     
         20 . The system of  claim 19 , wherein representing each constraint as a respective term equaling zero when the constraint is satisfied and equaling a strictly positive value when the constraint is not satisfied, and including each term in the QUBO formulation of the exchange problem comprises, for each equality constraint in the one or more constraints:
 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 term in the QUBO formulation of the exchange problem.   
     
     
         21 . The system of  claim 19 , wherein representing each constraint as a respective term equaling zero when the constraint is satisfied and equaling a strictly positive value when the constraint is not satisfied, and including each term in the QUBO formulation of the exchange problem comprises, for each inequality constraint in the one or more constraints:
 formulating the inequality constraint as an equality constraint comprising slack variables, wherein each slack variable is a binary variable;   representing the equality constraint comprising slack variables 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 term in the QUBO formulation of the exchange problem.