Systems and methods for solving combinatorial problems

摘要

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.