Quantum-inspired algorithms to solve intractable problems using classical computers

Patent metadata

Field	Value
Publication number	US-11983604-B2
Application number	US-202117378650-A
Country	US
Kind code	B2
Filing date	Jul 16, 2021
Priority date	Jul 16, 2021
Publication date	May 14, 2024
Grant date	May 14, 2024

Abstract

Systems and methods are configured to provide a first problem to be solved to a network of memristors. A second problem to be solved can be gradually provided to the network of memristors. Controlled noise can be applied to the network of memristors for at least a portion of time during which the second problem is “gradually” provided to the network of memristors. A solution to the second problem can be determined.

First claim

What is claimed is:

1. A computer-implemented method comprising:
providing, to a network of memristors, a first problem to be solved, the first problem corresponding with a curve for which a global minimum is previously determined;
gradually providing, to the network of memristors, a second problem to be solved that comprises incrementally solving for individual ones of a set of local minima to find the global minimum that is previously determined, wherein controlled noise is applied to the network of memristors for at least a portion of time during which the second problem is provided to the network of memristors,
wherein the second problem is gradually introduced to the first problem according to an adiabatic annealing process that reduces a compute time on the network of memristors for solving the second problem; and
determining a solution to the second problem.

2. The computer-implemented method of claim 1 , further comprising:
solving the first problem to determine an initial condition for the second problem.

3. The computer-implemented method of claim 1 , wherein the second problem is associated with a Hamiltonian, and wherein the method further comprises:
splitting the Hamiltonian associated with the second problem into at least a first Hamiltonian and a second Hamiltonian.

4. The computer-implemented method of claim 3 , further comprising:
controlling at least one of the first Hamiltonian or the second Hamiltonian with one or more gates to prevent influence of the first Hamiltonian or the second Hamiltonian on the solution.

5. The computer-implemented method of claim 3 , further comprising:
updating the first Hamiltonian based on received real-time data, wherein the second Hamiltonian is not updated based on the received real-time data.

6. The computer-implemented method of claim 3 , further comprising:
updating the second Hamiltonian based on received real-time data, wherein the first Hamiltonian is not updated based on the received real-time data.

7. The computer-implemented method of claim 1 , further comprising:
dividing the second problem into subsets, wherein each subset of the subsets is associated with a corresponding problem size, and
wherein gradually providing the second problem to be solved to the network of memristors comprises:
providing each subset of the subsets to the network of memristors in an order of increasing problem size.

8. The computer-implemented method of claim 1 , further comprising:
dividing the second problem into subsets, wherein each subset of the subsets is associated with a corresponding problem complexity, and
wherein gradually providing the second problem to be solved to the network of memristors comprises:
providing each subset of the subsets to the network of memristors in an order of increasing problem complexity.

9. The computer-implemented method of claim 1 , wherein the second problem is gradually introduced to the first problem that involves a transition from the first problem to the second problem, and wherein the second problem is not introduced when the first problem is introduced.

10. The computer-implemented method of claim 1 , wherein the second problem is gradually introduced to the first problem in accordance with formula:

P
=

1

t
ann

-

t
0

[

P
1

(

t

a
⁢
n
⁢
n

-

t
k

)

+

P
2

(

t
k

-

t
0

)

]

,

for
⁢

t
0

<

t
k

<

t

a
⁢
n
⁢
n

where t 0 is an initial time at which the second problem is introduced, t ann is a transition completion time, and t k is a time in between the initial time and the transition completion time.

11. The computer-implemented method of claim 1 , further comprising:
before gradually introducing the second problem to the first problem, applying a noise profile to an energy profile associated with the first problem, wherein the noise profile illustrates different levels of perturbations on the network of memristors at different times.

12. The computer-implemented method of claim 1 , further comprising:
before gradually introducing the second problem to the first problem, increasing a noise level associated with the first problem that transitions the network of memristors from a solution state to the first problem.

13. A system comprising:
at least one processor; and
a memory storing instructions that, when executed by the at least one processor, cause the system to perform a method comprising:
providing, to a network of memristors, a first problem to be solved, the first problem corresponding with a curve for which a global minimum is previously determined;
gradually providing, to the network of memristors, a second problem to be solved that comprises incrementally solving for individual ones of a set of local minima to find the global minimum that is previously determined, wherein controlled noise is applied to the network of memristors for at least a portion of time during which the second problem is provided to the network of memristors,
wherein the second problem is gradually introduced to the first problem according to an adiabatic annealing process that reduces a compute time on the network of memristors for solving the second problem; and
determining a solution to the second problem.

14. The system of claim 13 , wherein the instructions cause the system to perform the method further comprising:
solving the first problem to determine an initial conditi

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Kumar Suhas
• Strachan John Paul
• Van Vaerenbergh Thomas

Classifications

• G06N10/00 Primary

  Quantum computing, i.e. information processing based on quantum-mechanical phenomena · CPC title

• G06F9/455

  Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines · CPC title

• G06F30/3308 Primary

  using simulation · CPC title

• G06F30/27

  using machine learning, e.g. artificial intelligence, neural networks, support vector machines [SVM] or training a model · CPC title

• G06N3/044

  Recurrent networks, e.g. Hopfield networks · CPC title