System and method for performing fast computations using quantum counting based on simultaneous solutions to decision problem and associated hashing problem

Patent metadata

Field	Value
Publication number	US-11049034-B2
Application number	US-201715699669-A
Country	US
Kind code	B2
Filing date	Sep 8, 2017
Priority date	Jan 8, 2014
Publication date	Jun 29, 2021
Grant date	Jun 29, 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 estimating a number of the solutions to the decision problem using a quantum computer by determining if there is at least one simultaneous solution to both (i) the decision problem and (ii) an associated hashing problem. The method also includes increasing a precision of the estimated number of the solutions to the decision problem using the quantum computer by determining if there are multiple solutions to the decision problem that are simultaneously solutions to the associated hashing problem. The method further includes outputting or using the estimated number of the solutions to the decision problem as a solution to the computational problem.

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 simultaneous solution to both (i) the decision problem and (ii) an associated hashing problem;
using the quantum computer, increasing a precision of the estimated number of the solutions to the decision problem by determining if there are multiple solutions to the decision problem that are simultaneously solutions to the associated hashing problem; and
outputting or using the estimated number of the solutions to the decision problem as a solution to the computational problem;
wherein the hashing problem is associated with a hash function; and
wherein each solution to the hashing problem denotes a solution that obtains a specified random hash value from the hash function.

2. The method of claim 1 , wherein the hash function uses a random salt as part of hash computations.

3. The method of claim 1 , wherein the hash function is based on the discrete logarithm.

4. The method of claim 1 , wherein the associated hashing problem is solved efficiently with the quantum computer but cannot be solved efficiently with a classical computer.

5. The method of claim 1 , wherein:
the computational problem involves finding a percentile of a specified 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 specified 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 specified 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. The method of claim 1 , wherein the associated hashing problem is solvable for a sequence of N inputs using a quantum circuit having a size that is linear or approximately linear in N.

9. The method of claim 1 , wherein the hash function for a sequence of N inputs is constructed in the quantum computer as a first concatenated hash function with N first components, a permutation, and a second concatenated hash function with N second components.

10. The method of claim 9 , wherein:
a total number of output qubits for the hash function is b;
each of the first components of the first concatenated hash function has approximately (b/N+log 2 N) output qubits; and
each of the second components of the second concatenated hash function has approximately b/N output qubits.

11. 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:
determine, using the at least one quantum circuit, if there is at least one simultaneous solution to both (i) the decision problem and (ii) an associated hashing problem in order to estimate a number of the solutions to the decision problem; and
determine, using the at least one quantum circuit, if there are multiple solutions to the decision problem that are simultaneously solutions to the associated hashing problem in order to increase a precision of the estimated number of the solutions to the decision problem;

wherein the estimated number of the solutions to the decision problem represents a solution to the computational problem;
wherein the hashing problem is associated with a hash function; and
wherein each solution to the hashing problem denotes a solution that obtains a specified random hash value from the hash function.

12. The apparatus of claim 11 , wherein the hash function uses a random salt as part of hash computations.

13. The apparatus of claim 11 , wherein the associated hashing problem is solved efficiently with the quantum computer but cannot be solved efficiently with a classical computer.

14. The apparatus of claim 11 , wherein:
the computational problem involves finding a percentile of a specified 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.

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

16. The apparatus of claim 11 , 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 specified 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 j (x 1 , . . . , x d ) over the truncated inputs (x 1 , . . . , x d+1 ), where p i and p j are regression functions.

17. The apparatus of claim 11 , wherein the at least one quantum circuit comprises:
a first level of quantum circuits configured to implement a first concatenated hash function using N inputs; and
a second level of quantum circuits configured to implement a second concatenated hash function that operates on a permutation of outputs of the first level of quantum circuits.

18. The apparatus of claim 17 , wherein:
a total number of output qubits for the hash function is b;
each of the quantum circuits in the first level has approximately (b/N+log 2 N) output qubits; and
each of the quantum circuits in the second level has approximately b/N output qubits.

19. The apparatus of claim 11 , wherein:
the associated decision problem comprises a non-deterministic polynomial time (NP) class problem; and
the problem of counting the solutions to the associated decision problem comprises a #P class problem.

20. A system comprising:
a quantum computer comprising at least one quantum circuit; and
a classical computer comprising at least one processor configured to execute instructions stored in at least one memory;
wherein, to solve a computational problem that is reducible to a problem of counting solutions to an associated decision problem, the classical computer is configured to use the quantum computer to:
estimate a number of the solutions to the decision problem by determining if there is at least one simultaneous solution to both (i) the decision problem and (ii) an associated hashing problem; and
increase a precision of the estimated number of the solutions to the decision problem by determining if there are multiple solutions to the decision problem that are simultaneously solutions to the associated hashing problem;

wherein the estimated number of the solutions to the decision pr

Assignees

• Goldman Sachs & Co Llc

Inventors

• Burchard Paul
• Daoud Anthony

Classifications

• G06N7/01

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

• G06N10/20 Primary

  Models of quantum computing, e.g. quantum circuits or universal quantum computers · CPC title

• G06F1/0307

  Logarithmic or exponential functions (G06F1/0314, G06F1/035 take precedence) · CPC title

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• G06F17/17

  Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method ({G06F17/18 takes precedence } ; interpolation for numerical control G05B19/18) · CPC title