Generating quantum computing circuits by distributing approximation errors in a quantum algorithm

• US 10,664,761 B2
• Filed: 06/29/2018
• Issued: 05/26/2020
• Est. Priority Date: 05/25/2018
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Haener, Thomas, Roetteler, Martin H., Svore, Krysta M., Kliuchnikov, Vadym
• Primary Examiner(s): Alam, Mohammed
• Application Number:
  US16/023,206
• Publication Number:
  US 20190362270A1
• Time in Patent Office: 697 Days
• Field of Search: 716101
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 2119/06 Power analysis or power optimisation
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/337 Design optimisation
• CPC Class Codes: G06N 10/00 Quantum computing, i.e. information processing based on quantum-mechanical phenomena
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

Methods for generating quantum computing circuits by distributing approximation errors in a quantum algorithm are described. A method includes decomposing a quantum algorithm into quantum circuits. The method includes using at least one processor, automatically performing a step-wise decomposition of the quantum algorithm until the quantum algorithm is fully decomposed into the quantum circuits, where the automatically performing the step-wise decomposition results in a set of approximation errors and a set of parameters to instantiate at least a subset of the quantum circuits corresponding to the quantum algorithm, such that an overall approximation error caused by the automatically performing the step-wise decomposition is maintained below a specified threshold approximation error.

Claims

1. A method for decomposing a quantum algorithm into quantum circuits, the method comprising:

using at least one processor, automatically performing a step-wise decomposition of the quantum algorithm until the quantum algorithm is fully decomposed into the quantum circuits, wherein the automatically performing the step-wise decomposition results in a set of approximation errors and a set of parameters to instantiate at least a subset of the quantum circuits corresponding to the quantum algorithm, such that an overall approximation error caused by the automatically performing the step-wise decomposition is maintained below a specified threshold approximation error.

2. The method of claim 1, wherein each of the quantum circuits is a gate that can be implemented using a quantum processor.

3. The method of claim 1, wherein each of the quantum circuits is a fault-tolerant logical gate.

4. The method of claim 1, wherein each of the quantum circuits is implemented as a protected operation on encoded quantum data.

5. The method of claim 1 further comprising using an optimization problem minimizing a cost metric associated with implementing the quantum circuits while maintaining the overall approximation error below the specified threshold approximation error.

6. The method of claim 5, wherein the optimization problem encodes a condition to meet the overall approximation error and a condition to minimize the cost metric associated with the quantum circuits.

7. The method of claim 6, wherein the optimization problem is solved using a heuristic method to select parameters of the quantum circuits.

8. The method of claim 7, wherein the optimization problem is solved by choosing a random initial assignment of approximation errors and parameters.

9. The method of claim 8, wherein a solution to the optimization problem is computed using simulated annealing.

10. A method for decomposing a quantum algorithm into quantum circuits, the method comprising:

using at least one processor, automatically performing a step-wise decomposition of the quantum algorithm and distributing an overall approximation error caused by the automatically performing the step-wise decomposition into subroutines until the quantum algorithm is fully decomposed into the quantum circuits; and

using the at least one processor, minimizing a cost metric associated with implementing the quantum circuits while maintaining the overall approximation error below a specified threshold approximation error.

11. The method of claim 10, wherein each of the quantum circuits is implemented as a protected operation on encoded quantum data.

12. The method of claim 10, wherein the minimizing the cost metric further comprises solving an optimization problem using a heuristic method to select parameters of the quantum circuits.

13. The method of claim 12, wherein the optimization problem is solved by choosing a random initial assignment of approximation errors and parameters.

14. A computer-readable medium comprising computer executable instructions for a method comprising:

using at least one processor, automatically performing a step-wise decomposition of the quantum algorithm and distributing an overall approximation error caused by the automatically performing the step-wise decomposition into subroutines until the quantum algorithm is fully decomposed into the quantum circuits, wherein the step-wise decomposition into the subroutines is implemented via a quantum phase estimation (QPE) process; and

using the at least one processor, minimizing a cost metric associated with implementing the quantum circuits while maintaining the overall approximation error below a specified threshold approximation error.

15. The computer-readable medium of claim 14, wherein the QPE process implements a time evolution of an Ising model in a transverse field.

16. The computer-readable medium of claim 14, wherein the QPE process is applied to a task of evolving a quantum-mechanical system that is initialized in a given state for a specified total duration of time.

17. The computer-readable medium of claim 16, wherein the total duration of time is divided into subintervals.

18. The computer-readable medium of claim 17, wherein the total duration of time is divided into subintervals using Trotter method or Trotter-Suzuki method.

19. The computer-readable medium of claim 17, wherein the total duration of time is divided into subintervals using a Linear Combination of Unitaries (LCU) method.

20. The computer-readable medium of claim 19, wherein the LCU method is implemented using state preparation circuits.