Quantum computation for cost optimization problems

1. A computer-implemented method comprising:

receiving data representing a cost optimization problem in a network, wherein i) the network is represented as a graph of nodes and edges, and ii) each edge comprises an associated cost;

converting the data representing the cost optimization problem from a format that is associated with a classical computing resource into a format that is associated with a quantum computing resource, comprising mapping the data representing the cost optimization problem in a network to a quadratic unconstrained binary optimization (QUBO) formulation of the cost optimization problem, the QUBO formulation comprising multiple variables with values determined by states of respective qubits, wherein each qubit corresponds to a respective edge of the graph of nodes and edges;

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

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

2. The method of claim 1 , wherein the data representing a solution to the cost optimization problem comprises data representing a low energy configuration of states of the qubits, wherein the low energy configuration of the states of the qubits represents a low cost path in the graph of nodes and edges.

3. The method of claim 2 , wherein the low energy configuration of the states of the qubits comprise qubits in a 1 state and qubits in a 0 state, wherein the low cost path comprises edges corresponding to the qubits in a 1 state.

4. The method of claim 1 , wherein the cost optimization problem comprises determining a path between an initial node and an end node in the graph such that a sum of the associated costs of the constituent edges is minimized.

5. The method of claim 4 , wherein the received data representing a cost optimization problem in a network comprises data representing a first set of nodes, wherein the first set of nodes comprises an initial node for the path and an end node for the path.

6. The method of claim 5 , further comprising generating first constraints for the cost optimization, wherein the first constraints specify that, in a determined path, both the initial node and the end node comprise one incident edge.

7. The method of claim 6 , wherein the QUBO formulation of the cost optimization problem further comprises a Hamiltonian function represented by a matrix, and wherein mapping the data representing the cost optimization problem in a network to a QUBO formulation of the cost optimization problem comprises mapping the first constraint to the Hamiltonian function represented by a matrix, comprising, for each node in the first set of nodes:

identifying edges in the graph that are connected to the node;

populating entries of the matrix that correspond to the identified edges, the populating comprising:

adding −2k to diagonal entries of the matrix that correspond to the identified edges, wherein k represents a positive real number;

adding 4k to upper diagonal entries of the matrix that correspond to pairs of the identified edges; and

adding zero to lower diagonal entries of the matrix.

8. The method of claim 4 , wherein the received data representing a cost optimization problem in a network comprises data representing a second set of nodes, wherein the second set of nodes comprises mandatory nodes for the path.

9. The method of claim 8 , further comprising generating a second constraint for the cost optimization, wherein the second constraint i) specifies that, in a determined path, each mandatory node comprises two incident edges, and ii) penalizes candidate paths that do not include nodes in the second set of nodes.

10. The method of claim 9 , wherein the QUBO formulation of the cost optimization problem further comprises a Hamiltonian function represented by a matrix, and wherein mapping the data representing the cost optimization problem in a network to a QUBO formulation of the cost optimization problem comprises mapping the second constraint to the Hamiltonian function represented by a matrix, comprising, for each node in the second set of nodes:

identifying edges in the graph that are connected to the node;

populating entries of the matrix that correspond to the identified edges, the populating comprising:

adding −6k to diagonal entries of the matrix that correspond to the identified edges, where k represents a positive real number;

adding 4k to upper diagonal entries of the matrix that correspond to pairs of the identified edges; and

adding zero to lower diagonal entries of the matrix.

11. The method of claim 4 , wherein the received data representing a cost optimization problem in a network comprises data representing a third set of nodes, wherein the third set of nodes comprise prohibited nodes for the path.

12. The method of claim 11 , further comprising generating a third constraint for the cost optimization, wherein the third constraint i) specifies that, in a determined path, each prohibited node comprises zero incident edges, and ii) penalizes candidate paths that include nodes in the third set of nodes.

13. The method of claim 12 , wherein the QUBO formulation of the cost optimization problem further comprises a Hamiltonian function represented by a matrix, and wherein mapping the data representing the cost optimization problem in a network to a QUBO formulation of the cost optimization problem comprises mapping the third constraint to the Hamiltonian function represented by a matrix, comprising, for each node in the third set of nodes:

identifying edges in the graph that are connected to the node;

populating entries of the matrix that correspond to the identified edges, the populating comprising:

adding 2k to diagonal entries of the matrix that correspond to the identified edges, where k represents a positive real number; and

adding zero to other entries of the matrix.

14. The method of claim 4 , wherein the received data representing a cost optimization problem in a network comprises data representing a fourth set of nodes, wherein the fourth set of nodes comprise nodes to be removed from the graph.

15. The method of claim 14 , further comprising generating a fourth constraint for the cost optimization, wherein the fourth constraint removes the nodes in the fourth set of nodes from the graph.

16. The method of claim 4 , wherein the received data representing a cost optimization problem in a network comprises data representing the received data representing a cost optimization problem in a network comprises data representing:

a first set of nodes, wherein the first set of nodes comprises an initial node for the path and an end node for the path,

a second set of nodes, wherein the second set of nodes comprises mandatory nodes for the path,

a third set of nodes, wherein the third set of nodes comprise prohibited nodes for the path, and

a fourth set of nodes, wherein the fourth set of nodes comprise nodes to be removed from the graph.

17. The method of claim 16 , further comprising generating a fifth constraint for the cost optimization, wherein the fifth constraint specifies that, in a determined path, each node in a fifth set of nodes comprising a complement of a union of the first, second, third and fourth sets of nodes comprises zero or two incident edges.

18. The method of claim 17 , wherein the QUBO formulation of the cost optimization problem further comprises a Hamiltonian function represented by a matrix, and wherein mapping the data representing the cost optimization problem in a network to a QUBO formulation of the cost optimization problem comprises:

introducing an additional auxiliary qubit;

mapping the fifth constraint to the Hamiltonian function represented by a matrix, comprising, for each node in the fifth set of nodes:

identifying edges in the graph that are connected to the node;

populating entries of the matrix that correspond to the identified edges, the populating comprising:

adding 2k to diagonal entries of the matrix that correspond to the identified edges, where k represents a positive real number,

adding 4k to upper diagonal entries of the matrix that correspond to pairs of the identified edges,

adding zero to lower diagonal entries of the matrix;

adding 8k to a diagonal entry of the matrix that corresponds to the auxiliary qubit; and

adding −8k to entries in a column and row corresponding to the auxiliary qubit and the identified edges.

19. The method of claim 1 , wherein initiating an action based on the obtained data representing a solution to the cost optimization problem comprises initiating distribution of goods according to a route specified by the solution to the cost optimization problem.

20. 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 a cost optimization problem in a network, wherein i) the network is represented as a graph of nodes and edges, and ii) each edge comprises an associated cost;

converting the data representing the cost optimization problem from a format that is associated with a classical computing resource into a format that is associated with a quantum computing resource, comprising mapping the data representing the cost optimization problem in a network to a quadratic unconstrained binary optimization (QUBO) formulation of the cost optimization problem, the QUBO formulation comprising multiple variables with values determined by states of respective qubits, wherein each qubit corresponds to a respective edge of the graph of nodes and edges;

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

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