Quantum processor based systems and methods that minimize a continuous variable objective function

Patent metadata

Field	Value
Publication number	US-9424526-B2
Application number	US-201414280204-A
Country	US
Kind code	B2
Filing date	May 16, 2014
Priority date	May 17, 2013
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

Computational techniques for mapping a continuous variable objective function into a discrete variable objective function problem that facilitate determining a solution of the problem via a quantum processor are described. The modified objective function is solved by minimizing the cost of the mapping via an iterative search algorithm.

First claim

The invention claimed is:

1. A non-transitory computer-readable storage medium containing processor-executable instructions, which when executed cause at least one digital processor to:
receive a first objective function comprising a plurality of non-binary variables;
receive a plurality of integers which represent the plurality of non-binary variables;
define or receive a number of bits used per integer in the plurality of integers proportional to a quotient from division of a number of qubits in a quantum computer by the number of integers in the plurality of integers, wherein the quantum computer is communicatively coupled to the at least one digital processor;
receive a cost matrix comprising a number of values for a number of neighboring integers in the plurality of integers;
generate a mapping function, wherein the mapping function maps the plurality of integers to a plurality of bit strings and each bit string comprises the number of bits used per integer;
generate a second objective function comprising a sum over the values for the neighboring integers in the cost matrix wherein the neighboring integers correspond to bit strings that are separated by a Hamming distance of one;
minimize the second objective function;
generate a third objective function comprising a subset of the plurality of bit strings;
send the third objective function to the quantum computer;
solve the third objective function via the quantum computer; and
receive a solution to the third objective function from the quantum computer.

2. The computer-readable storage medium of claim 1 wherein the plurality of non-binary variables comprises a set of continuous variables.

3. The computer-readable storage medium of claim 2 wherein the instructions when executed cause the at least one digital processor further to:
draw a sample from the set of continuous variables; and
define the plurality of integers as indices to the sample drawn from the set of continuous variables.

4. The computer-readable storage medium of claim 1 wherein the cost matrix comprises values defined in a piecewise way, parameterized by a difference between the neighboring integers, where if:
the difference is zero or one the values are zero; and
the difference is two or more the values are proportional to a positive value raised to the power of the difference minus two.

5. The computer-readable storage medium of claim 1 wherein the instructions when executed cause the at least one digital processor further to:
run a tabu search to minimize the second objective function.

6. The computer-readable storage medium of claim 1 wherein the instructions when executed cause the at least one digital processor further to:
run a search selected from the group consisting of: a local search, an iterative search, a simulated annealing search, a path-relinking algorithm, and a generic algorithm.

7. A method of operation of a computational solver system to solve a continuous variable problem, the method comprising:
defining a first objective function comprising a set of continuous variables via a digital computer;
defining a number for a plurality of integers to sample from the set of continuous variables via the digital computer;
defining a number of bits used per integer in the plurality of integers via the digital computer, wherein the number of bits used per integer is proportional to a quotient from division of a number of qubits in a quantum computer by the number of integers in the plurality of integers, and wherein the quantum computer is communicatively coupled to the digital computer;
defining a cost matrix of neighboring integers via the digital computer;
generating a mapping function via the digital computer, wherein the mapping function maps the set of continuous variables to a set of discrete variables and each discrete variable comprising the number of bits used per integer;
generating an objective function comprising neighboring integers in the cost matrix wherein the neighboring integers correspond to a pair of discrete variables in the set of discrete variables that are separated by a Hamming distance of one;
minimizing the second objective function via the digital computer;
generating a third objective function comprising the set of discrete variables via the digital computer; and
solving the third objective function via the quantum computer.

8. The method of claim 7 wherein the cost matrix comprises values defined in a piecewise way, parameterized by a difference between the neighboring integers, where if:
the difference is zero or one the values are zero; and
the difference is two or more the values are proportional to a positive value raised to the power of the difference minus two.

9. The method of claim 7 wherein minimizing the second objective function via the digital computer, includes:
running a tabu search.

10. The method of claim 7 wherein minimizing the second objective function via the digital computer includes running a search selected from the group consisting of: local search, an iterative search, a simulated annealing search, a path-relinking algorithm, and a generic algorithm.

11. The method of claim 7 wherein the set of discrete variables are bit strings and generating a mapping function includes generating the mapping function that maps the plurality of integers to a set of bit strings.

12. A hybrid computational system, the system comprising:
a digital computer comprising at least one digital processor and at least one nontransitory processor-readable medium communicatively coupled with the at least one digital processor, and which in operation:
receives a first objective function comprising a plurality of non-binary variables,
receives a plurality of integers which represent the plurality of non-binary variables,
receives a cost matrix comprising values for a number of neighboring integers in the plurality of integers,
generates a mapping function, wherein the mapping function maps the plurality of integers to a plurality of bit strings,
generates a second objective function comprising a sum over the values for the neighboring integers in the cost matrix wherein the neighboring integers correspond to bit strings that are separated by a Hamming distance of one,
minimizes the second objective function, and
creates a third objective function comprising a subset of the plurality of bit strings;

a quantum processor which in operation solves a continuous variable problem; and
a communication channel which in operation communicatively couples the digital computer to the quantum processor, wherein the digital computer defines a number of bits used per integer in the plurality of integers proportional to a quotient from division of a number of qubits in the quantum processor by the number of integers in the plurality of integers and each bit string comprises the number of bits used per integer, and wherein the quantum processor in operation:
receives the third objective function from the digital computer, and
creates a solution to the third objective function.

13. The system of claim 12 wherein the quantum processor provides a source of samples to the third objective function.

Assignees

• D Wave Systems Inc

Inventors

• Ranjbar Mani

Classifications

• G06N99/002 Primary

  Physics · mapped topic

• B82Y10/00

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

• 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

• G06N10/60 Primary

  Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms · CPC title