Systems and methods for solving combinatorial problems
View Patent ↗Systems and methods to solve combinatorial problems employ a permutation network which may be modeled after a sorting network where comparators are replaced by switches that controllably determine whether inputs are swapped or are left unchanged at the outputs. A quantum processor may be used to generate permutations by the permutation network by mapping the state of each switch in the network to the state of a respective qubit in the quantum processor. In this way, a quantum computation may explore all possible permutations simultaneously to identify a permutation that satisfies at least one solution criterion. The Travelling Salesman Problem is discussed as an example of a combinatorial problem that may be solved using these systems and methods.
1. A method of operation of a computational solver system to solve a problem, the method comprising:
defining an objective function by a digital computer, the objective function operable to receive a bit string as an input and produce a real number as an output;
defining a permutation network by a digital computer, wherein the permutation network comprises a plurality of inputs, a plurality of outputs, a plurality of switches, and a plurality of paths, and wherein each path maps a respective input to a respective output through a respective combination of switches;
mapping the permutation network from the digital computer to a quantum processor, the quantum processor which comprises a plurality of qubits, wherein mapping the permutation network from the digital computer to a quantum processor includes controlling the state of at least one switch in the permutation network by the state of at least one qubit of the plurality of qubits;
generating a permutation from the permutation network by the quantum processor, wherein the permutation corresponds to a configuration of at least one of the plurality of switches that produces an arrangement of at least one of the plurality of outputs;
returning the permutation by the quantum processor to the digital computer, wherein returning the permutation by the quantum processor to the digital computer includes reading out the state of the at least one qubit in the plurality of qubits;
determining a characteristic of the permutation by the digital computer by evaluating the objective function using the permutation as the input to produce a result comprising a real number as the output, wherein the characteristic of the permutation is based at least in part on the result;
evaluating the characteristic of the permutation against a set of at least one solution criterion by the digital computer; and
in response to the characteristic of the permutation not satisfying the set of at least one solution criterion, repeating the generating a permutation, determining a characteristic of the permutation, and evaluating the characteristic of the permutation until the set of at least one solution criterion is satisfied.
2. The method of claim 1 wherein the quantum processor includes a programming subsystem and an evolution subsystem, and wherein:
mapping the permutation network from the digital computer to the quantum processor includes programming the quantum processor by the programming subsystem, wherein programming the quantum processor includes assigning a respective energy to each configuration of switches in the permutation network; and
generating a permutation by the quantum processor includes evolving the quantum processor by the evolution subsystem to determine a configuration of switches in the permutation network.
3. The method of claim 2 wherein evolving the quantum processor by the evolution subsystem to determine a configuration of switches in the permutation network includes evolving the quantum processor by the evolution subsystem to determine a specific configuration of switches in the permutation network that corresponds to a low-value of the objective function.
4. The method of claim 3 wherein evolving the quantum processor by the evolution subsystem to determine a specific configuration of switches in the permutation network that corresponds to a low-value of the objective function includes evolving the quantum processor by the evolution subsystem to determine a specific configuration of switches in the permutation network that corresponds to a ground state value of the objective function.
5. The method of claim 2 wherein evolving the quantum processor by the evolution subsystem to determine a configuration of switches in the permutation network includes performing at least one of adiabatic quantum computation and/or quantum annealing by the quantum processor.
6. The method of claim 2 wherein repeating the generating a permutation, determining a characteristic of the permutation, and evaluating the characteristic of the permutation until the set of at least one solution criterion is satisfied includes iteratively shaping a probability distribution of the quantum processor until a permutation that satisfies the set of at least one solution criterion is found.
7. The method of claim 1 wherein the problem includes a combinatorial optimization problem.
8. The method of claim 1 wherein evaluating the characteristic of the permutation against a set of at least one solution criterion by the digital computer includes evaluating whether or not the value of the objective function that corresponds to the permutation satisfies the set of at least one solution criterion by the digital computer.
9. The method of claim 8 wherein evaluating whether or not the value of the objective function that corresponds to the permutation satisfies the set of at least one solution criterion by the digital computer includes evaluating whether or not the value of the objective function that corresponds to the permutation satisfies at least one of: a minimum allowed value, a maximum allowed value, a minimum allowed computation time, a maximum allowed computation time, a minimum allowed number of iterations, or a maximum allowed number of iterations.
10. The method of claim 1 wherein defining a permutation network by the digital computer comprises:
defining a sorting network by the digital computer, wherein the sorting network comprises a number of inputs, a number of outputs, a set of comparators, and a set of paths, and wherein each path maps a respective input to a respective output through a respective combination of comparators such that each input respectively maps to each of the outputs through a respective path; and
programmatically replacing each comparator in the set of comparators with a respective switch by the digital computer.
11. The method of claim 10 wherein the sorting network includes at least one of: a bubble sorting network, an insertion sorting network, a bitonic sorting network, a Batcher's merge-exchange sorting network, a Bose-Nelson sorting network, a Hibbard sorting network, or a Batcher odd-even mergesort sorting network.
12. The method of claim 1 wherein defining a permutation network by the digital computer includes defining a permutation network wherein the number of outputs is greater than the number of inputs by the digital computer.
13. The method of claim 12 wherein generating a permutation by the permutation network includes mapping each input to a respective output by the permutation network.
14. The method of claim 13 wherein mapping each input to a respective output by the permutation network includes determining a configuration of the switches of the permutation that maps each input to a respective output.
15. The method of claim 1 wherein each input is selectively mappable to each of the outputs through a respective path.
16. A computational solver system for solving problems, the computational solver system comprising:
a digital computer that:
defines an objective function by a digital computer, the objective function operable to receive a bit string as an input and produce a real number as an output;
defines a permutation network for generating permutations by a permutation network definition module, wherein the permutation network comprises a plurality of inputs, a plurality of outputs, a plurality of switches, and a plurality of paths, and wherein each path maps a respective input to a respective output through a respective combination of switches such that each input respectively maps to each of the outputs through a respective path;
determines a characteristic of each permutation generated by the permutation network by a characteristic determination module; and
evaluates the characteristic of the permutation against a set of at least one solution criterion by an evaluation module; and
a quantum processor in communication with the digital computer, the quantum processor comprising a plurality of qubits, wherein the computational solver system maps the permutation network from the digital computer to the quantum processor, wherein the state of at least one switch in the permutation network is controlled by the state of at least one qubit of the plurality of qubits, and generates permutations by the quantum processor, and wherein each permutation corresponds to a configuration of the switches that produces an arrangement of the outputs.
17. The computational solver system of claim 16 wherein the quantum processor includes a superconducting quantum processor comprising superconducting qubits.
18. The computational solver system of claim 16 wherein the quantum processor includes at least one of a processor that performs adiabatic quantum computation and/or a processor that performs quantum annealing.
19. The system of claim 16 wherein the quantum processor comprises:
a plurality of qubits;
a programming subsystem that programs the quantum processor by assigning a respective energy to each configuration of switches in the permutation network;
an evolution subsystem that evolves the quantum processor to determine a configuration of switches in the permutation network; and
a read-out subsystem that reads out a state of each qubit in the plurality of qubits.