Pebbling strategies for quantum memory management

Patent metadata

Field	Value
Publication number	US-11615334-B2
Application number	US-201916457408-A
Country	US
Kind code	B2
Filing date	Jun 28, 2019
Priority date	Dec 19, 2018
Publication date	Mar 28, 2023
Grant date	Mar 28, 2023

Abstract

Quantum memory management is becoming a pressing problem, especially given the recent research effort to develop new and more complex quantum algorithms. The disclosed technology concerns various example memory management schemes for quantum computing. For example, certain embodiments concern methods for managing quantum memory based on reversible pebbling games constructed from SAT-encodings.

First claim

What is claimed is:

1. A method to manage quantum memory, comprising:
implementing a straight-line program via a sequence of quantum operations while guaranteeing a given total bound on available quantum memory.

2. The method of claim 1 , wherein each node of the program corresponds to a quantum circuit from a set of library operations.

3. The method of claim 2 , wherein the library operations comprise in-place operations and out-of-place operations.

4. The method of claim 1 , further comprising computing a dependency graph structure for the straight-line program.

5. The method of claim 4 , where the dependency graph structure, together with the given total bound on available memory, is used to encode an instance of a satisfiability (SAT) problem.

6. The method of claim 5 , further comprising using a SAT solver to attempt to solve the SAT problem.

7. The method of claim 6 , wherein the SAT problem is a solvable SAT problem, and wherein the method further comprises constructing a solution to the SAT problem where the solution corresponds to a reversible pebble game.

8. The method of claim 7 , further comprising translating the reversible pebble game into a quantum circuit to compute the straight-line program.

9. The method of claim 1 , wherein the method further comprises trading off a number of qubits relative to a size or depth of a quantum circuit to implement a function in the quantum circuit.

10. The method of claim 9 , wherein the trading off is performed by constructing one or more pebble games on a dependency graph.

11. The method of claim 1 , wherein the method further comprises:
constructing a SAT problem to determine the sequence of quantum operations;
using a SAT solver to attempt to solve the SAT problem;
receiving an indication that the SAT solver failed in an attempt;
adjusting a number of available qubits; and
repeating use of the SAT solver to attempt to solve the adjusted SAT problem.

12. The method of claim 1 , wherein the method further comprises:
constructing a SAT problem to determine the sequence of quantum operations;
using a SAT solver to attempt to solve the SAT problem;
receiving an indication that the SAT solver failed in an attempt;
executing a bounded-model checking solver to generate mathematical evidence that no solution to the pebble game with a given number of steps and a given number of pebbles can be constructed, or executing PDR (Property Directed Reachability) to generate mathematical evidence that no solution to the pebble game with a given number of pebbles can be constructed.

13. A method, comprising:
constructing a satisfiability (SAT) problem to determine a sequence of quantum operations implementing a quantum circuit and to be executed by a defined number of available qubits in a quantum computing device; and
using a SAT solver to attempt to solve the SAT problem.

14. The method of claim 13 , further comprising:
receiving an indication that the SAT solver failed in an attempt;
adjusting a number of available qubits; and
repeating use of the SAT solver to attempt to solve the adjusted SAT problem.

15. The method of claim 13 , wherein a solution to the SAT problem corresponds to a reversible pebble game.

16. The method of claim 13 , further comprising translating the solution to the SAT into an implementable description of the sequence of quantum operations.

17. The method of claim 16 , further comprising:
loading the sequence of elementary quantum gates into the quantum computing device; and
operating the quantum computing device to execute the quantum circuit.

18. A quantum computing device, comprising:
a compiled quantum computer circuit description including a plurality of quantum circuits, the compiled quantum computer circuit description configured to program one or more quantum processing units to execute a sequence of elementary quantum gates generated by:
implementing a straight-line program via a sequence of quantum operations while guaranteeing a given total bound on available quantum memory.

19. The quantum computing device of claim 18 , wherein the compiled quantum computer circuit description is further configured to program one or more quantum processing units to execute a sequence of elementary quantum gates generated by:
constructing a SAT problem to determine the sequence of quantum operations;
using a SAT solver to attempt to solve the SAT problem;
receiving an indication that the SAT solver failed in an attempt;
adjusting a number of available qubits; and
repeating use of the SAT solver to attempt to solve the adjusted SAT problem.

20. The quantum computing device of claim 19 , wherein the SAT problem is a solvable SAT problem, and wherein the compiled quantum computer circuit description is further configured to program one or more quantum processing units to execute a sequence of elementary quantum gates generated by:
constructing a solution to the SAT problem where the solution corresponds to a reversible pebble game.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Roetteler Martin
• Meuli Giulia

Classifications

• G06N10/60 Primary

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

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N10/00 Primary

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

• G06N5/003

  Physics · mapped topic