# US 11,113,620 B2 · Enhancing simulated annealing with quantum annealing > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,113,620 B2 - Document ID: US11113620B2 - Status: Granted - Kind: B2 - Application number: 16/067,338 - Filed: 2016-12-22 - Published: 2019-01-17 - Granted: 2021-09-07 - Earliest claimed: 2015-12-30 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Hartmut Neven - Web page: https://patentgrep.com/patent/US11113620B2 ## CPC - G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms - G06F 15/163: Interprocessor communication - G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods and apparatus for enhancing simulated annealing with quantum fluctuations. In one aspect, a method includes obtaining an input state; performing simulated annealing on the input state with a temperature reduction schedule until a decrease in energy is below a first minimum value; terminating the simulated annealing in response to determining that the decrease in energy is below the first minimum level; outputting a first evolved state and first temperature value; reducing the temperature to a minimum temperature value; performing quantum annealing on the first evolved state with a transversal field increase schedule until a completion of a second event occurs; terminating the quantum annealing in response to determining that a completion of the second event has occurred; outputting a second evolved state as a subsequent input state for the simulated annealing, and determining that the completion of the first event has occurred. ## Claims ### Claim 1 A method for performing thermal annealing with quantum fluctuations, the method comprising: obtaining an initial input state; performing simulated annealing and quantum annealing on the initial input state and subsequent input states until a completion of a first event; and determining that the completion of the first event has occurred wherein the quantum annealing comprises: creating a list of connected subgraphs; computing a lowest achievable energy value for each connected subgraph; computing the difference between a current energy value and the lowest achievable energy value for each connected subgraph; determining that at least one difference is positive; selecting the subgraph and corresponding transition that achieves an overall largest positive difference; and performing the corresponding transition that achieves the overall largest positive difference. ### Claim 2 (depends on 1) The method of claim 1, wherein performing simulated annealing and quantum annealing on the initial input state and subsequent input states comprises: receiving an input state, the input state being one of the initial input state or a subsequent input state; performing simulated annealing on the input state with a temperature reduction schedule until a decrease in energy is below a first minimum value; terminating the simulated annealing in response to determining that the decrease in energy is below the first minimum level; outputting a first evolved state and first temperature value; reducing the simulated annealing temperature to a minimum temperature value; performing quantum annealing on the first evolved state with a transversal field increase schedule until a completion of a second event occurs; terminating the quantum annealing in response to determining that a completion of the second event has occurred; and outputting a second evolved state as a subsequent input state for the simulated annealing. ### Claim 3 (depends on 2) The method of claim 2, wherein determining that the completion of the first event has occurred comprises determining that the first temperature value is lower or equal to the minimum temperature value. ### Claim 4 (depends on 2) The method of claim 2, wherein performing simulated annealing on the input state with a temperature reduction schedule comprises performing a Metropolis algorithm. ### Claim 5 (depends on 2) The method of claim 2, wherein performing quantum annealing comprises repeating a number of sweeps of quantum annealing until the completion of the second event occurs. ### Claim 6 (depends on 2) The method of claim 2, wherein performing quantum annealing comprises repeating a number of sweeps of quantum annealing until a decrease in energy is below a second minimum value, wherein the second minimum value is different from the first minimum value. ### Claim 7 (depends on 1) The method of claim 1, wherein the initial input state is a state of a physical system whose ground state encodes the solution to an optimization task. ### Claim 8 (depends on 7) The method of claim 7, wherein determining that the completion of the first event has occurred further comprises performing a measurement on the first evolved state output with the first temperature value to determine the solution to the optimization task. ### Claim 9 (depends on 1) The method of claim 1, wherein the connected subgraphs are of a size K less than a system size. ### Claim 10 (depends on 9) The method of claim 9, wherein the number of repeated sweeps is at most QS N/K, wherein QS is a predetermined number of quantum sweeps and N is a system size. ### Claim 11 (depends on 1) The method of claim 1, wherein completion of a second event occurs when either (i) a fixed number of quantum sweeps have been performed, or (ii) the lowest achievable energy value for each connected subgraph is the same or higher than the current energy value. ### Claim 12 (depends on 1) The method of claim 1, wherein selecting the subgraph and corresponding transition that achieves the overall largest positive difference further comprises: calculating a Hamming distance for each connected subgraph in a set of connected subgraphs that achieves the overall lowest achievable energy value; determining that there is one subgraph with a shortest Hamming distance relative to the Hamming distance of other subgraphs; and choosing the transition that has the shortest Hamming distance in response to determining that there is one subgraph with the shortest Hamming distance. ### Claim 13 (depends on 12) The method of claim 12, further comprising: determining that there is more than one subgraph with a shortest Hamming distance; and choosing the transition from the set of subgraphs that achieve the overall lowest achievable energy value and that have the shortest Hamming distance at random. ### Claim 14 (depends on 1) The method of claim 1, wherein the initial input state is a randomly chosen state. ### Claim 15 (depends on 1) The method of claim 1, wherein the initial input state is a classical state. ### Claim 16 (depends on 15) The method of claim 15, wherein preparing the classical state comprises setting the temperature to a predetermined maximum value. ### Claim 17 An apparatus comprising: an annealing system comprising a quantum system in communication with an auxiliary system, the annealing system configured to: obtain an initial input state; perform simulated annealing and quantum annealing on the initial input state and subsequent input states until a completion of a first event; and determine that the completion of the first event has occurred, wherein the quantum annealing comprises: creating a list of connected subgraphs; computing a lowest achievable energy value for each connected subgraph; computing the difference between a current energy value and the lowest achievable energy value for each connected subgraph; determining that at least one difference is positive; selecting the subgraph and corresponding transition that achieves an overall largest positive difference; and performing the corresponding transition that achieves the overall largest positive difference. ### Claim 18 (depends on 17) The apparatus of claim 17, wherein the auxiliary system acts as a thermal bath for the quantum system. ### Claim 19 An apparatus comprising: an annealing system comprising a quantum integrated circuit in communication with a classical integrated circuit, the annealing system configured to: obtain an initial input state; perform simulated annealing and quantum annealing on the initial input state and subsequent input states until a completion of a first event; and determine that the completion of the first event has occurred, wherein the quantum annealing comprises: creating a list of connected subgraphs; computing a lowest achievable energy value for each connected subgraph; computing the difference between a current energy value and the lowest achievable energy value for each connected subgraph; determining that at least one difference is positive; selecting the subgraph and corresponding transition that achieves an overall largest positive difference; and performing the corresponding transition that achieves the overall largest positive difference.