Training a quantum optimizer

Patent metadata

Field	Value
Publication number	US-10176433-B2
Application number	US-201715457914-A
Country	US
Kind code	B2
Filing date	Mar 13, 2017
Priority date	May 13, 2016
Publication date	Jan 8, 2019
Grant date	Jan 8, 2019

Abstract

Among the embodiments disclosed herein are variants of the quantum approximate optimization algorithm with different parametrization. In particular embodiments, a different objective is used: rather than looking for a state which approximately solves an optimization problem, embodiments of the disclosed technology find a quantum algorithm that will produce a state with high overlap with the optimal state (given an instance, for example, of MAX-2-SAT). In certain embodiments, a machine learning approach is used in which a “training set” of problems is selected and the parameters optimized to produce large overlap for this training set. The problem was then tested on a larger problem set. When tested on the full set, the parameters that were found produced significantly larger overlap than optimized annealing times. Testing on other random instances (e.g., from 20 to 28 bits) continued to show improvement over annealing, with the improvement being most notable on the hardest problems. Embodiments of the disclosed technology can be used, for example, for near-term quantum computers with limited coherence times.

First claim

What is claimed is:

1. A method of operating a quantum computing device, comprising:
causing a quantum computing device to evolve from a first state to a second state according to a schedule that is neither annealing nor adiabatic, the first state corresponding to a first Hamiltonian, the second state corresponding to a second Hamiltonian, wherein the schedule includes an X schedule for Hamiltonian terms in the X basis, and a Z schedule for Hamiltonian terms in the Z basis, and wherein the schedule is nonlinear or piecewise linear in the X schedule, the Z schedule, or both the X schedule and the Z schedule.

2. The method of claim 1 , wherein the schedule includes one or more sequences where the X schedule and the Z schedule converge toward one another and one or more sequences where the X schedule and the Z schedule diverge from one another.

3. The method of claim 1 , wherein the X schedule and the Z schedule intersect only in a latter half of the respective schedules.

4. The method claim 1 , wherein one or both of the X schedule or the Z schedule has terms that vary and wherein the variation in terms is greater in a latter half of the respective schedule than in a front half of the respective schedule.

5. The method of claim 1 , further comprising generating the schedule by performing a schedule-training process beginning from an initial schedule, wherein the initial schedule includes one or more of:
(a) an initial X schedule for Hamiltonian terms in the X basis and an initial Z schedule for Hamiltonian terms in the Z basis, and wherein the initial X schedule and the initial Z schedule are both constant;
(b) an initial X schedule for Hamiltonian terms in the X basis and an initial Z schedule for Hamiltonian terms in the Z basis, and wherein one of the initial X schedule or the initial Z schedule is constant, and the other one of the initial X schedule or the initial Z schedule is nonconstant;
(c) an initial X schedule for Hamiltonian terms in the X basis and an initial Z schedule for Hamiltonian terms in the Z basis, and wherein one of the initial X schedule or the initial Z schedule is linear, and the other one of the initial X schedule or the initial Z schedule is nonlinear and nonconstant;
(d) an initial X schedule for Hamiltonian terms in the X basis and an initial Z schedule for Hamiltonian terms in the Z basis, and wherein one or both of the initial X schedule or the initial Z schedule have terms that vary with greater degree in a latter half of the respective schedule;
(e) an initial X schedule for Hamiltonian terms in the X basis and an initial Z schedule for Hamiltonian terms in the Z basis, and wherein one or both of the initial X schedule or the initial Z schedule have terms that vary with greater degree in a latter half of the respective schedule; or
(f) an initial X schedule for Hamiltonian terms in the X basis and an initial Z schedule for Hamiltonian terms in the Z basis, and wherein one or both of the initial X schedule or the initial Z schedule have terms that are constant in a first half of the respective schedule and that vary in a second half of the respective schedule.

6. The method of claim 1 , wherein the second Hamiltonian is a solution to an optimization problem, and wherein the schedule-training process uses one or more training problems.

7. The method of claim 1 , further comprising generating the schedule by:
modifying an initial schedule from its initial state to create a plurality of modified schedules;
testing the modified schedules relative to one or more problem instances;
selecting one of the modified schedules based on an observed improvement in solving one or more of the problem instances.

8. The method of claim 7 , wherein the generating further comprises iterating the acts of modifying, testing, and selecting until no further improvement is observed in the selected modified schedule.

9. The method of claim 1 , wherein, for at least one step of the Z schedule or X schedule, the sign of the Z schedule or X schedule step is opposite of the sign of the respective final step of the Z schedule or X schedule.

10. The method of claim 1 , wherein, for at least one step of the Z schedule or X schedule, the sign of the Z schedule or X schedule step switches from positive to negative or vice versa.

11. The method of claim 1 , wherein one or more terms of the first Hamiltonian are noncommuting with corresponding terms of the second Hamiltonian.

12. A method, comprising:
generating a learned schedule for controlling a quantum computing device by performing a schedule-training process beginning from an initial schedule, wherein the initial schedule includes an initial X schedule for Hamiltonian terms in the X basis and an initial Z schedule for Hamiltonian terms in the Z basis.

13. The method of claim 12 , wherein at least one of the initial X schedule or the initial Z schedule is nonlinear.

14. The method of claim 12 , wherein the initial X schedule and the initial Z schedule are both constant.

15. The method of claim 12 , wherein one of the initial X schedule or the initial Z schedule is constant, and the other one of the initial X schedule or the initial Z schedule is nonconstant.

16. The method of claim 12 , wherein one of the initial X schedule or the initial Z schedule is linear, and the other one of the initial X schedule or the initial Z schedule is nonlinear and nonconstant.

17. The method of claim 12 , wherein one or both of the initial X schedule or the initial Z schedule have terms that vary with greater degree in a latter half of the respective schedule.

18. The method of claim 12 , wherein one or both of the initial X schedule or the initial Z schedule have terms that are constant in a first half of the respective schedule and that vary in a second half of the respective schedule.

19. The method of claim 12 , wherein the learned schedule includes one of:
(a) a learned X schedule for Hamiltonian terms in the X basis and a learned Z schedule for Hamiltonian terms in the Z basis, wherein the learned schedule includes one or more sequences where the learned X schedule and the learned Z schedule converge toward one another and one or more sequences where the learned X schedule and the learned Z schedule diverge from one another;
(b) a learned X schedule for Hamiltonian terms in the X basis and a learned Z schedule for Hamiltonian terms in the Z basis, wherein the learned X schedule and the learned Z schedule intersect only in a latter half of the respective schedules;
(c) a learned X schedule for Hamiltonian terms in the X basis and a learned Z schedule for Hamiltonian terms in the Z basis, and wherein one or both of the learned X schedule or the learned Z schedule have terms that vary and wherein the variation in terms is greater in a latter half of the respective schedule than in a front half of the respective schedule;
(d) a learned X schedule for Hamiltonian terms in the X basis and a learned Z schedule for Hamiltonian terms in the Z basis, and wherein, for at least one step of the learned Z schedule or learned X schedule, the sign of the learned Z schedule or learned X schedule step is opposite of the sign of the respective final step of the learned Z schedule or learned X schedule; or
(e) a learned X schedule for Hamiltonian terms in the X basis and a learned Z schedule for Hamiltonian terms in the Z basis, and wherein, for at least one step of the learned Z schedule or learned X schedule, the sign of the learned Z schedule or learned X schedule step switches from positive to negative or vice

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Hastings Matthew
• Wecker David

Classifications

• G06N5/013

  Automatic theorem proving · CPC title

• G06N99/005

  Physics · mapped topic

• G06N99/002 Primary

  Physics · mapped topic

• G06N5/006

  Physics · mapped topic

• G06N10/80

  Quantum programming, e.g. interfaces, languages or software-development kits for creating or handling programs capable of running on quantum computers; Platforms for simulating or accessing quantum computers, e.g. cloud-based quantum computing · CPC title