Systems and methods for solving computational problems

Patent metadata

Field	Value
Publication number	US-9405876-B2
Application number	US-201414186895-A
Country	US
Kind code	B2
Filing date	Feb 21, 2014
Priority date	Jun 17, 2009
Publication date	Aug 2, 2016
Grant date	Aug 2, 2016

Abstract

Solving computational problems may include generating a logic circuit representation of the computational problem, encoding the logic circuit representation as a discrete optimization problem, and solving the discrete optimization problem using a quantum processor. Output(s) of the logic circuit representation may be clamped such that the solving involves effectively executing the logic circuit representation in reverse to determine input(s) that corresponds to the clamped output(s). The representation may be of a Boolean logic circuit. The discrete optimization problem may be composed of a set of miniature optimization problems, where each miniature optimization problem encodes a respective logic gate from the logic circuit representation. A quantum processor may include multiple sets of qubits, each set coupled to respective annealing signal lines such that dynamic evolution of each set of qubits is controlled independently from the dynamic evolutions of the other sets of qubits.

First claim

We claim:

1. A method of performing a quantum annealing operation using a quantum processor comprising a first annealing signal line, a second annealing signal line, a first set of qubits and at least a second set of qubits, the method comprising:
clamping a respective state of each qubit in the first set of qubits by applying a first dynamic annealing signal to each qubit in the first set of qubits, wherein the first annealing signal line communicably couples the first dynamic annealing signal to each qubit in the first set of qubits; and
evolving a respective state of each qubit in the second set of qubits by applying a second dynamic annealing signal to each qubit in the second set of qubits, wherein the second annealing signal line communicably couples the second dynamic annealing signal to each qubit in the second set of qubits, and
wherein the first dynamic annealing signal that is applied to each qubit in the first set of qubits is evolved to compensate for a change induced in each qubit in the first set of qubits by a coupling to the second dynamic annealing signal that is applied to each qubit in the second set of qubits.

2. The method of claim 1 wherein the quantum processor further comprises a third set of qubits, and wherein the method further comprises:
applying a third dynamic annealing signal to each qubit in the third set of qubits, wherein the first, second and third dynamic annealing signals are controlled independently from one another.

3. The method of claim 1 wherein the respective state of each qubit in the first set of qubits is clamped as TRUE.

4. The method of claim 1 wherein the respective state of each qubit in the first set of qubits is clamped as FALSE.

5. The method of claim 1 further comprising: mapping a logic circuit representation of a computational problem to the first set of qubits, at least the second set of qubits, a first set of coupling devices, and at least a second set of coupling devices in a quantum processor.

6. The method of claim 5 wherein evolving the respective state of each qubit in the second set of qubits by applying the second dynamic annealing signal to each qubit in the second set of qubits determines a solution to the logic circuit representation of the computational problem.

7. The method of claim 5 wherein evolving the respective state of each qubit in the second set of qubits by applying the computational problem is selected from a group consisting of constraint satisfaction problems, discrete optimization problems, sets of miniature optimization problems, and factoring problems.

8. The method of claim 5 wherein the evolving the respective state of each qubit in the second set of qubits by applying the second dynamic annealing signal to each qubit in the second set of qubits minimizes the computational problem, and the computational problem is minimized when the logic circuit representation of the computational problem is obeyed.

9. A quantum processor comprising:
a first set of qubits;
a first annealing signal line that is configured to communicably couple a first dynamic annealing signal to each qubit in the first set of qubits to clamp a respective state of each qubit in the first set of qubits;
a second set of qubits; and
a second annealing signal line that is configured to communicably couple a second dynamic annealing signal to each qubit in the second set of qubits to evolve a respective state of each qubit in the second set of qubits, wherein at least one qubit in the first set of qubits is configured to communicably couple to at least one qubit in the second set of qubits, and
wherein the first dynamic annealing signal that is applied to each qubit in the first set of qubits is evolved to compensate for a change induced in each qubit in the first set of qubits by a coupling to the second dynamic annealing signal that is applied to each qubit in the second set of qubits.

10. The quantum processor of claim 9 , further comprising:
a third set of qubits; and
a third annealing signal line that is configured to communicably couple a third dynamic annealing signal to each qubit in the third set of qubits, wherein at least one qubit in the third set of qubits is configured to communicably couple to at least one qubit in the second set of qubits.

11. The quantum processor of claim 9 wherein the respective state of each qubit in the first set of qubits is clamped as TRUE.

12. The quantum processor of claim 9 wherein the respective state of each qubit in the first set of qubits is clamped as FALSE.

Assignees

• D Wave Systems Inc

Inventors

• Macready William
• Rose Geordie
• Mahon Thomas
• Love Peter
• Drew-Brook Marshall

Classifications

• G06F17/11

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F30/327 Primary

  Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist · CPC title

• B82Y10/00 Primary

  Nanotechnology for information processing, storage or transmission, e.g. quantum computing or single electron logic · CPC title

• G06N99/002

  Physics · mapped topic

• G06F17/505 Primary

  Physics · mapped topic