Quantum-walk-based algorithm for classical optimization problems

Patent metadata

Field	Value
Publication number	US-11694103-B2
Application number	US-201916530916-A
Country	US
Kind code	B2
Filing date	Aug 2, 2019
Priority date	Sep 19, 2018
Publication date	Jul 4, 2023
Grant date	Jul 4, 2023

Abstract

Example circuit implementations of Szegedy's quantization of the Metropolis-Hastings walk are presented. 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.

First claim

The invention claimed is:

1. A method of operating a quantum computing device, comprising:
implementing a quantum walk procedure of a Markov chain Monte Carlo simulation in which an underlying classical walk is obtained using a Metropolis-Hastings rotation or a Glauber dynamics rotation, wherein the method comprises any one or more of:
preparing a move register in a uniform superposition of all bit locations


ϕ
〉

M

=

1

N

⁢

∑

j
=
1

N

⁢


j
〉

M

;

copying the state of the left register onto the right register, resulting in
|ϕ M ⊗|x L ⊗|x R ;

conditioned on the state of the move register, flipping the j-th bit of the left register:

∑
y

⁢

T
yx

⁢


j
〉

M

⊗



y
j

〉

L

⊗


x
〉

R

,

where y j is x with the j-th bit flipped;

using the left and right registers to evaluate A xy and prepare a coin register in state
√{square root over ( A yx |)}0 C +√{square root over (1− A yx |)}1 C ;

uncomputing the move register by looking up the coordinate where the left and right registers differ; and
implementing the transformation

∑
y

⁢

T
yx

⁡

(

1
-

A
yx

)

⁢


y
〉

L

⊗


x
〉

R

⊗


1
〉

C

→

1
-

∑
y

⁢

T
yx

⁢

A
yx

⁢


x
〉

L

⊗


x
〉

R

⊗


0
〉

C

.

wherein T yz represents a transition of a Metropolis-Hastings walk, N represents a number of qubits, j represents a qubit, |ϕ M is a state of a move register, |x L is a state of a left register, |x R is a state of a right register, A yx is a minimum energy difference, defined as A yx =min (1, e β[E(x)−E(y)] ), wherein β is inverse temperature, |j M corresponds to a j th qubit of the move register, |y j L corresponds to a j th qubit of the left register, and C denotes the coin register.

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. A method of operating a quantum computing device, comprising: implementing a quantum walk procedure of a Markov chain Monte Carlo simulation 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 and follows:
Ũ W =RV†B\FBV,
wherein f(j) is f(z j ), wherein z j is one of N elements of a set of moves M
V→Σ j √{square root over ( f ( j )|)} j M ,

B→|x S |j M (√{square root over (1− A x·z j ,x )}|0 + A x·z j ,x |1 ) C ,

F→|x·z j b S |j M |b C ,
R→−| 0 M| 0 C ,, and | j M |b →|j M |b for ( j,b )≠(0,0),

U W represents a quantum walk, V represents a move preparation, F represents a spin flip, R represents a reflection and B represents a Boltzmann coi

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Troyer Matthias
• Poulin David
• Heim Bettina
• Lemieux Jessica

Classifications

• G06N10/20

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

• G06N10/60 Primary

  Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms · CPC title

• G06F18/295

  Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models · CPC title

• G06F30/20

  Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) · CPC title

• G06N10/00 Primary

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