Search

EP-3837645-B1 - A QUANTUM-WALK-BASED ALGORITHM FOR CLASSICAL OPTIMIZATION PROBLEMS

EP3837645B1EP 3837645 B1EP3837645 B1EP 3837645B1EP-3837645-B1

Inventors

  • TROYER, MATTHIAS
  • SVORE, KRYSTA
  • HEIM, Bettina
  • POULIN, David

Dates

Publication Date
20260506
Application Date
20190919

Claims (6)

  1. A method of operating a quantum computing device, the quantum computing device comprising a system register comprised of n qubits, a move register comprised of N qubits, and a coin register comprised of a single qubit, the method comprising: implementing a quantum walk procedure := RW † Λ W of a Markov chain Monte Carlo simulation on the quantum computing device, where W is an oracle transformation defined as W | x 〉 ⊗ |0〉 = | w x 〉 ⊗ | x 〉, in which an underlying classical walk is obtained using a Metropolis-Hastings rotation or a Glauber dynamics rotation, wherein the quantum walk procedure is performed with only a logarithmic depth, wherein uses a quantum circuit which acts on states of the form x S z M b C , where := Y † Y , Y : x ⊗ y → x ⊗ x ⋅ y if x ⋅ y ∈ M 0 else . , and is a set of moves, where | x 〉 S is the state of the system register; | z 〉 M is the state of the move register; and | b 〉 C is the state of the coin register; and where the quantum circuit is performed using the sequence of quantum gates U ˜ W = RV † B † FBV , where V : 0 M → ∑ j = 1 N f j j M , where f is uniform over a set of moves and zero otherwise, with | | = N « 2 n and f ( j ) = f ( z i ), where the z j are the N elements of ; B : x S j M 0 C → x S j M 1 − A x ⋅ z j , x 0 + A x ⋅ z j , x 1 C , where move x → y = x · z j of the underlying classical walk is accepted with probability A y,x ; F : x S j M b C → x ⋅ z j b S j M b C ; and R : 0 M 0 C → − 0 M 0 C , j M b → j M b for j b ≠ 0 0 .
  2. The method of claim 1, wherein the quantum walk procedure is performed using binary encodings of the move registers.
  3. The method of claim 1, wherein the quantum walk procedure is performed using unary encodings of the move registers.
  4. The method of claim 1, wherein the underlying classical walk is obtained using a Metropolis-Hastings rotation and the quantum walk procedure is performed using a Boltzmann coin having a coin register that is rotated using the Metropolis-Hastings rotation.
  5. The method of claim 1, wherein the underlying classical walk is obtained using a Glauber dynamics rotation and the quantum walk procedure is performed using a Boltzmann coin having a coin register that is rotated using the Glauber dynamics rotation.
  6. The method of claim 1, where the quantum walk procedure comprises implementing a Boltzmann coin using lookup tables and conditional quantum gates.

Description

FIELD This application concerns quantum computing. Non-patent literature document DANIEL REITZNER ET AL: "Quantum Walks", ACTA PHYSICA SLOVACA., vol. 61, no. 6, 15 May 2013 (2013-05-15), discloses a method of operating a quantum computing device, comprising implementing a quantum walk procedure of a Markov chain Monte Carlo simulation. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a graph showing an example minimum total time to solution (min(TTS)) as a function of system size for a one dimensional Ising model at β = 2.FIGS. 2 and 3 are a series of graphs showing an example minimum total time to solution (min(TTS)) as a function of system size for a sample of 100 random instances of the Ising model; in particular, graph 200 of FIG. 2 shows the median TTS in the illustrated example, and graph 300 of FIG. 3 llustrates the average of 10% of the hardest example instances relative to the classical walk.FIG. 4 illustrates a generalized example of a suitable classical computing environment in which several of the described embodiments can be implemented.FIG. 5 illustrates an example of a possible network topology (e.g., a client-server network) for implementing a system according to the disclosed technology.FIG. 6 illustrates another example of a possible network topology (e.g., a distributed computing environment) for implementing a system according to the disclosed technology.FIG. 7 illustrates an exemplary system for implementing the disclosed technology.FIG. 8 is a flow chart illustrating one example method for performing an embodiment of the disclosed advancments in quantum computing.FIG. 9 is a flow chart illustrating another example method for performing an embodiment of the disclosed advancments in quantum computing.FIG. 10 is a flow chart illustrating a further example method for performing an embodiment of the disclosed advancments in quantum computing. SUMMARY The invention is defined in the appended independent claim 1. Preferred embodiments of the invention are set out in the appended dependent claims. In this disclosure, example circuit implementations of Szegedy's quantization of the Metropolis-Hastings walk are presented. This quantum walk is usually defined with respect to an oracle. A direct implementation of this oracle requires costly arithmetic operations. As discussed herein, and in accordance with the disclosed technology, the quantum walk can be reformulated in a way that circumvents the problems of any previous approach. Also disclosed herein are heuristic quantum algorithms that use the quantum walk in the context of discrete optimization problems. Numerous studies of the resulting performances are also presented. The numerical results indicate polynomial quantum speedups in heuristic settings. In certain disclosed embodiments, a quantum walk procedure of a Markov chain Monte Carlo simulation is implemented in which a quantum move register is reset at every step in the quantum walk. In further embodiments, a quantum walk procedure of a Markov chain Monte Carlo simulation is implemented in which an underlying classical walk is obtained using a Metropolis-Hastings rotation or a Glauber dynamics rotation. In some embodiments, a quantum walk procedure is performed in the quantum computing device to implement a Markov Chain Monte Carlo method; during the quantum walk procedure, an intermediate measurement is obtained; and a rewinding procedure of one or more but not all steps of the quantum walk procedure is performed if the intermediate measurement produces an incorrect outcome. Any of the disclosed embodiments can be performed by one or more computer-readable media storing computer-executable instructions which when executed by a computer cause the computer to perform any of the disclosed methods. Any of the disclosed embodiments can also be implemented in a system, comprising a quantum computing device; and a classical computer in communication with and configured to control the quantum computing device, wherein the quantum computing device and the classical computer collectively operate to perform any of the disclosed methods. DETAILED DESCRIPTION I. Introduction The disclosed technology involves the issue of accelerating Markov chain Monte Carlo (MCMC) simulations on a quantum computer using quantum walks. More generally, MCMC simulations are used in sampling from arbitrary distributions, Gibbs sampling, optimization, simulated annealing, and related methods. Quantum computers accelerate MCMC simulations by implementing them as quantum walks. In order to accomplish this acceleration, a Markov transition matrix is desirably implemented in embodiments of the disclosed technology as a walk oracle. Embodiments of the disclosed technology concern the implementation of such oracles for accelerating MCMC algorithms in which the random walk might stay at the same location in one time step. Detailed example implementations of such oracles have heretofore been unknown. This disclosure presents exampl