Quantum assisted optimization
Methods and apparatus for quantum assisted optimization. In one aspect, a method includes obtaining a set of initial input states, applying one or more of (i) dynamical thermal fluctuations and (ii) cluster update algorithms to the set of input states and subsequent input states when the states evolve within the classical information processors, applying dynamical quantum fluctuations to the set of input states and subsequent states when the states evolve within the quantum systems and repeating the application steps until a desirable output state is obtained.
1. A method performed by classical information processors, the method comprising:
for a graph partitioned into one or more local regions, the graph representing a quantum system included in a quantum processor, the quantum system comprising a plurality of interacting qubits, wherein the plurality of qubits are represented by respective nodes in the graph, interactions between qubits are represented by respective edges between nodes, a ground state of the quantum system encodes a solution to an optimization task, and the graph is partitioned into the one or more local regions according to a division of the optimization task and embedding capabilities of the quantum processor:
repeatedly, until a target output state that approximates the ground state to within a predetermined threshold is obtained:
applying one or more of (i) dynamical thermal fluctuations or (ii) cluster update algorithms to an initial input state of the quantum system or a subsequent input state to obtain a classically evolved state for the repetition;
for each local region, determining whether application of the (i) dynamical thermal fluctuations or (ii) cluster update algorithms are failing to overcome one or more energy barriers in an energy landscape at a given temperature, wherein each energy barrier of the one or more energy barriers is associated with a respective local region of the one or more local regions;
for each local region for which it is determined that the application of the (i) dynamical thermal fluctuations or (ii) cluster update algorithms has failed to overcome one or more energy barriers, providing the classically evolved state for the repetition to the quantum processor for application of dynamical quantum fluctuations to the classically evolved state for the repetition, wherein the dynamical quantum fluctuations are only applied, at the given temperature, to qubits of the quantum processor that are represented by graph nodes in the local regions of the graph that are associated with the one or more energy barriers that application of the (i) dynamical thermal fluctuations or (ii) cluster update algorithms fail to overcome;
obtaining, from the quantum processor, an output state;
determining whether the output state is the target output state; and
in response to determining that the output state is not the target output state, providing the output state as an input state for a subsequent repetition; or
in response to determining that the output state is the target output state, determining a solution to the optimization task through measurement of the output state.
2. The method of claim 1 , wherein the dynamical thermal fluctuations comprise:
tempered transitions, wherein applying the tempered transitions comprise applying a parallel tempering algorithm; or
weighted dynamical tempered transitions, wherein applying the weighted dynamical tempered transitions comprise applying annealing importance sampling.
3. The method of claim 1 , wherein the cluster update algorithms create:
non-local state transformation in parameter space in various different temperatures; or
non-local isothermal state transformation in parameter space, wherein applying the cluster update algorithms comprise applying Houdayers cluster move algorithm.
4. The method of claim 1 , wherein the dynamical quantum fluctuations comprise increasing and decreasing zero-temperature quantum fluctuations or increasing and decreasing finite-temperature dissipative quantum fluctuations.
5. The method of claim 1 , further comprising partitioning the graph into local regions according to the optimization task.
6. The method of claim 1 , wherein determining whether the output state is the target output state comprises determining whether the output states converge to the predetermined threshold.
7. A system comprising one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
for a graph partitioned into one or more local regions, the graph representing a quantum system included in a quantum processor, the quantum system comprising a plurality of interacting qubits, wherein the plurality of qubits are represented by respective nodes in the graph, interactions between qubits are represented by respective edges between nodes, a ground state of the quantum system encodes a solution to an optimization task, and the graph is partitioned into the one or more local regions according to a division of the optimization task and embedding capabilities of the quantum processor:
repeatedly, until a target output state that approximates the ground state to within a predetermined threshold is obtained:
applying one or more of (i) dynamical thermal fluctuations or (ii) cluster update algorithms to an initial input state of the quantum system or a subsequent input state to obtain a classically evolved state for the repetition;
for each local region, determining whether application of the (i) dynamical thermal fluctuations or (ii) cluster update algorithms are failing to overcome one or more energy barriers in an energy landscape at a given temperature, wherein each energy barrier of the one or more energy barriers is associated with a respective local region of the one or more local regions;
for each local region for which it is determined that the application of the (i) dynamical thermal fluctuations or (ii) cluster update algorithms has failed to overcome one or more energy barriers, providing the classically evolved state for the repetition to the quantum processor for application of dynamical quantum fluctuations to the classically evolved state for the repetition, wherein the dynamical quantum fluctuations are only applied, at the given temperature, to qubits of the quantum processor that are represented by graph nodes in the local regions of the graph that are associated with the one or more energy barriers that application of the (i) dynamical thermal fluctuations or (ii) cluster update algorithms fail to overcome;
obtaining, from the quantum processor, an output state;
determining whether the output state is the target output state; and
in response to determining that the output state is not the target output state, providing the output state as an input state for a subsequent repetition; or
in response to determining that the output state is the target output state, determining a solution to the optimization task through measurement of the output state.
8. The system of claim 7 , wherein the dynamical thermal fluctuations comprise:
tempered transitions, wherein applying the tempered transitions comprise applying a parallel tempering algorithm; or
weighted dynamical tempered transitions, wherein applying the weighted dynamical tempered transitions comprise applying annealing importance sampling.
9. The system of claim 7 , wherein the cluster update algorithms create:
non-local state transformation in parameter space in various different temperatures; or non-local isothermal state transformation in parameter space, wherein applying the cluster update algorithms comprise applying Houdayers cluster move algorithm.
10. The system of claim 7 , wherein the dynamical quantum fluctuations comprise increasing and decreasing zero-temperature quantum fluctuations or increasing and decreasing finite-temperature dissipative quantum fluctuations.
11. The system of claim 7 , further comprising partitioning the graph into local regions according to the optimization task.
12. The system of claim 7 , wherein determining whether the output state is the target output state comprises determining whether the output states converge to the predetermined threshold.
13. A non-transitory computer-readable storage medium comprising instructions stored thereon that are executable by a processing device and upon such execution cause the processing device to perform operations for training a machine learning model to predict computer memory failures, the operations comprising:
for a graph partitioned into one or more local regions, the graph representing a quantum system included in a quantum processor, the quantum system comprising a plurality of interacting qubits, wherein the plurality of qubits are represented by respective nodes in the graph, interactions between qubits are represented by respective edges between nodes, a ground state of the quantum system encodes a solution to an optimization task, and the graph is partitioned into the one or more local regions according to a division of the optimization task and embedding capabilities of the quantum processor:
repeatedly, until a target output state that approximates the ground state to within a predetermined threshold is obtained:
applying one or more of (i) dynamical thermal fluctuations or (ii) cluster update algorithms to an initial input state of the quantum system or a subsequent input state to obtain a classically evolved state for the repetition;
for each local region, determining whether application of the (i) dynamical thermal fluctuations or (ii) cluster update algorithms are failing to overcome one or more energy barriers in an energy landscape at a given temperature, wherein each energy barrier of the one or more energy barriers is associated with a respective local region of the one or more local regions;
for each local region for which it is determined that the application of the (i) dynamical thermal fluctuations or (ii) cluster update algorithms has failed to overcome one or more energy barriers, providing the classically evolved state for the repetition to the quantum processor for application of dynamical quantum fluctuations to the classically evolved state for the repetition, wherein the dynamical quantum fluctuations are only applied, at the given temperature, to qubits of the quantum processor that are represented by graph nodes in the local regions of the graph that are associated with the one or more energy barriers that application of the (i) dynamical thermal fluctuations or (ii) cluster update algorithms fail to overcome;
obtaining, from the quantum processor, an output state;
determining whether the output state is the target output state; and
in response to determining that the output state is not the target output state, providing the output state as an input state for a subsequent repetition; or
in response to determining that the output state is the target output state, determining a solution to the optimization task through measurement of the output state.
14. The non-transitory computer-readable storage medium of claim 13 , wherein the dynamical thermal fluctuations comprise:
tempered transitions, wherein applying the tempered transitions comprise applying a parallel tempering algorithm; or
weighted dynamical tempered transitions, wherein applying the weighted dynamical tempered transitions comprise applying annealing importance sampling.
15. The non-transitory computer-readable storage medium of claim 13 , wherein the cluster update algorithms create:
non-local state transformation in parameter space in various different temperatures; or
non-local isothermal state transformation in parameter space, wherein applying the cluster update algorithms comprise applying Houdayers cluster move algorithm.
16. The non-transitory computer-readable storage medium of claim 13 , wherein the dynamical quantum fluctuations comprise increasing and decreasing zero-temperature quantum fluctuations or increasing and decreasing finite-temperature dissipative quantum fluctuations.
17. The non-transitory computer-readable storage medium of claim 13 , further comprising partitioning the graph into local regions according to the optimization task.
18. The non-transitory computer-readable storage medium of claim 13 , wherein determining whether the output state is the target output state comprises determining whether the output states converge to the predetermined threshold.