Accuracy and time-to-solution in solving combinatorial optimization problems with quantum annealers by using anneal offsets
AssigneeQC Ware Corp.
InventorsJuan Ignacio Adame, Peter McMahon
Life of this patent
Estimating the term…
Abstract
Quantum computing is a computational paradigm for solving (exactly or approximately) difficult combinatorial optimization problems. One degree of freedom that is available is the so-called annealing schedule, which defines how the quantum computation evolves from the start of the computation to the end of the computation. This schedule is defined by anneal offsets, which can be different for each quantum bit (qubit) in the quantum computer. The choice of annealing schedule can have a dramatic impact on the performance of the computer. In this disclosure we provide a method for selecting and/or modifying the annealing schedule based on the problem to be solved.
Claims20
A method implemented on a digital computer system comprising a processor, the processor executing instructions to effect a method for solving a combinatorial optimization problem using a quantum computing device, the method comprising:
- receiving coefficients hi and Jij that define a combinatorial optimization problem to minimize G=Σihisi+Σ(i,j)Jiksisj with respect to qubits si;
- determining an annealing schedule of anneal offsets δi for the qubits si based on a magnitude of a local field Fi of each qubit si, where Fi({sk})=hi+ΣkJiksk and +the summation is over indices k for which k≠i and Jik≠0;
- and
- configuring and causing a quantum computing device to obtain a solution to the combinatorial optimization problem G using the annealing schedule δi.
A method implemented on a digital computer system comprising a processor, the processor executing instructions to effect a method for solving a combinatorial optimization problem using a quantum computing device, the method comprising:
- receiving coefficients hi and Jij that define a combinatorial optimization problem to minimize G=Σihisi+Σ(i,j)Jijsisj with respect to qubits si;
- repeatedly for multiple iterations:
- determining an annealing schedule of anneal offsets δi for the qubits si;
- and
- configuring and causing a quantum computing device to obtain a solution to the combinatorial optimization problem G using the annealing schedule δi;
- wherein, for at least one of the interations, the annealing schedule of anneal offsets δi is based on a magnitude of a local field F1 of each qubit si, where Fi({sk})=hi+ΣkJiksk and the summation is over indices k for which k≠i and Jik≠0;
- and
- selecting from among the solutions obtained in the multiple iterations.
A computing system for solving a combinatorial optimization problem, comprising:
- a digital computer system;
- and
- a quantum computing device;
- wherein the digital computer system:
- receives coefficients hi and Jij that define a combinatorial optimization problem to minimize G=Σihisi+Σ(i,j)Jijsisj with respect to qubits si;
- determines an annealing schedule of anneal offsets δi for the qubits si based on a magnitude of a local field Fi of each qubit si, where Fi({sk})=hi+ΣkJiksk and the summation is over indices k for which k≠i and Jik≠0;
- and
- configures and causes the quantum computing device to obtain a solution to the combinatorial optimization problem G using the annealing schedule δi.
Dependencies are inferred from the claim text.