System and method for performing fast computations using quantum counting and pseudo-random sets

Patent metadata

Field	Value
Publication number	US-11170305-B2
Application number	US-201815906217-A
Country	US
Kind code	B2
Filing date	Feb 27, 2018
Priority date	Jan 8, 2014
Publication date	Nov 9, 2021
Grant date	Nov 9, 2021

Abstract

A method is provided for solving a computational problem that is reducible to a problem of counting solutions to an associated decision problem. The method includes, using a quantum computer, estimating a number of the solutions to the decision problem by determining if there is at least one solution to the decision problem that lies in a pseudo-random set. The method also includes outputting or using the estimated number of the solutions to the decision problem as a solution to the computational problem. Determining if there is at least one solution to the decision problem that lies in the pseudo-random set could include determining if there is a sequence of solutions to the decision problem that, taken together, lies in the pseudo-random set.

First claim

What is claimed is:

1. A method for solving a computational problem that is reducible to a problem of counting solutions to an associated decision problem, the method comprising:
using a quantum computer, estimating a number of the solutions to the decision problem by determining if there is at least one solution to the decision problem that lies in a pseudo-random set; and
outputting or using the estimated number of the solutions to the decision problem as a solution to the computational problem;
wherein determining if there is at least one solution to the decision problem that lies in the pseudo-random set comprises determining if there is a sequence of solutions to the decision problem that, taken together, lies in the pseudo-random set; and
wherein the method further comprises generating the pseudo-random set using the quantum computer by:
using multiple seeds to generate multiple first component pseudo-random sets;
performing a permutation of qubits in the first component pseudo-random sets;
using results of the permutation to generate multiple second component pseudo-random sets; and
combining the second component pseudo-random sets.

2. The method of claim 1 , wherein:
the sequence of solutions comprises N solutions, where N is an integer greater than one;
each of the first component pseudo-random sets represents a superposition of N pseudo-random values;
the permutation comprises a circular shift; and
each of the second component pseudo-random sets represents a superposition of N 2 sets of pseudo-random values.

3. A method for solving a computational problem that is reducible to a problem of counting solutions to an associated decision problem, the method comprising:
using a quantum computer, estimating a number of the solutions to the decision problem by determining if there is at least one solution to the decision problem that lies in a pseudo-random set; and
outputting or using the estimated number of the solutions to the decision problem as a solution to the computational problem;
wherein determining if there is at least one solution to the decision problem that lies in the pseudo-random set comprises determining if there is a sequence of solutions to the decision problem that, taken together, lies in the pseudo-random set wherein the sequence of solutions comprises N solutions, where Nis an integer greater than one; and
wherein at least one of:
the quantum computer has multiple quantum circuits configured to generate the pseudo-random set, the quantum circuits having a size that is linear with N; or
an error associated with the estimated number of the solutions to the decision problem decreases at a rate of 1/N.

4. The method of claim 1 , wherein determining if there is at least one solution to the decision problem that lies in the pseudo-random set comprises using Grover's quantum search algorithm.

5. The method of claim 1 , wherein:
the computational problem involves finding a percentile of a function ƒ(x) over inputs x; and
the associated decision problem involves deciding whether there is an input x such that ƒ(x)<c for a given value of c.

6. The method of claim 1 , wherein:
the computational problem involves finding an average, sum, or integral of a function ƒ(x) over inputs x; and
the associated decision problem involves deciding whether there is a pair (x, y) for which y<ƒ(x).

7. The method of claim 1 , wherein:
the computational problem involves finding a conditional expectation p( ) over inputs (x 1 , . . . , x d ), where p(x 1 , . . . , x d )=ƒ(x 1 , . . . , x d ; average x d+1 p(x 1 , . . . , x d+1 )) for a function ƒ( ) over truncated inputs (x 1 , . . . , x d ; a); and
the associated decision problem involves computing averages of p(x 1 , . . . , x d+1 )p i (x 1 , . . . , x d ) and p i (x 1 , . . . , x d )p j (x 1 , . . . , x d ) over the truncated inputs (x 1 , . . . , x d+1 ), where p i and p j are regression functions.

8. An apparatus comprising:
a quantum computer comprising at least one quantum circuit;
wherein, to solve a computational problem that is reducible to a problem of counting solutions to an associated decision problem, the quantum computer is configured to use the at least one quantum circuit to estimate a number of the solutions to the decision problem by determining if there is at least one solution to the decision problem that lies in a pseudo-random set;
wherein the estimated number of the solutions to the decision problem represents a solution to the computational problem;
wherein, to determine if there is at least one solution to the decision problem that lies in the pseudo-random set, the quantum computer is configured to use the at least one quantum circuit to determine if there is a sequence of solutions to the decision problem that, taken together, lies in the pseudo-random set; and
wherein the at least one quantum circuit is configured to generate the pseudo-random set by:
using multiple seeds to generate multiple first component pseudo-random sets;
performing a permutation of qubits in the first component pseudo-random sets;
using results of the permutation to generate multiple second component pseudo-random sets; and
combining the second component pseudo-random sets.

9. The apparatus of claim 8 , wherein:
each of the seeds comprises log 2 r qubits and log 2 N zero qubits, where r denotes an estimated size of a solution set and N denotes a number of solutions in the sequence of solutions;
each of the first component pseudo-random sets comprises approximately (log 2 r+log 2 N) qubits and represents a superposition of N intermediate values;
the permutation comprises a circular shift; and
each of the second component pseudo-random sets represents a superposition of N 2 intermediate values.

10. An apparatus comprising:
a quantum computer comprising at least one quantum circuit;
wherein, to solve a computational problem that is reducible to a problem of counting solutions to an associated decision problem, the quantum computer is configured to use the at least one quantum circuit to estimate a number of the solutions to the decision problem by determining if there is at least one solution to the decision problem that lies in a pseudo-random set wherein the estimated number of the solutions to the decision problem represents a solution to the computational problem;
wherein, to determine if there is at least one solution to the decision problem that lies in the pseudo-random set, the quantum computer is configured to use the at least one quantum circuit to determine if there is a sequence of solutions to the decision problem that, taken together, lies in the pseudo-random set;
wherein the sequence of solutions comprises N solutions, where Nis an integer greater than one; and
wherein at least one of:
the at least one quantum circuit comprises multiple quantum circuits configured to generate the pseudo-random set, the multiple quantum circuits having a size that is linear with N; or
an error associated with the estimated number of the solutions to the decision problem decreases at a rate of 1/N.

11. The apparatus of claim 8 , wherein:
the computational problem involves finding a percentile of a function ƒ(x) over inputs x; and
the associated decision problem involves deciding whether there is an input x such that ƒ(x)<c for a given value of c.

12. The apparatus of claim 8 , wherein:
the computational problem involves finding an average, sum, or integral of a function ƒ(x) over inputs x; and
the associated decision problem involves deciding whether there is a pair (x, y) for which y<ƒ(x).

13. The apparatus of claim 8 , where

Assignees

• Goldman Sachs & Co Llc

Inventors

• Burchard Paul

Classifications

• G06N7/01 Primary

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06N5/013 Primary

  Automatic theorem proving · CPC title

• G06N10/40

  Physical realisations or architectures of quantum processors or components for manipulating qubits, e.g. qubit coupling or qubit control · CPC title

• H04L9/3006

  underlying computational problems or public-key parameters · CPC title

• G06F7/582

  Pseudo-random number generators · CPC title