Monte Carlo Markov chain based quantum program optimization

Patent metadata

Field	Value
Publication number	US-11651232-B2
Application number	US-201816052348-A
Country	US
Kind code	B2
Filing date	Aug 1, 2018
Priority date	Aug 1, 2018
Publication date	May 16, 2023
Grant date	May 16, 2023

Abstract

From a quantum program a first mutant is generated using a processor and a memory, where the first mutant is a randomly-generated transformation of the quantum program. A quality score, a correctness distance, and a probability of acceptance corresponding to the first mutant are computed. An acceptance corresponding to the first mutant is determined according to the probability of acceptance. Upon determining that an acceptance of the first mutant corresponding to the probability of acceptance exceeds an acceptance threshold, the quantum program is replaced with the first mutant. Upon determining that the quality score exceeds a storage threshold and that the correctness distance is zero, the first mutant is stored. These actions are iterated until reaching an iteration limit.

First claim

What is claimed is:

1. A method comprising:
iterating, until reaching an iteration limit, actions comprising:
generating, from a quantum program using a processor and a memory, a first mutant, the first mutant comprising a transformation of the quantum program, wherein the quantum program comprises a set of operations, each operation in the set of operations specifying at least one gate operating on at least one qubit, wherein the transformation comprises inserting, into the set of operations, a synthesized operation comprising an instance of a gate type and at least one qubit on which the instance operates, wherein an insertion point, the gate type, and the at least one qubit of the synthesized operation are randomly selected;
computing a quality score, a correctness distance, and a probability of acceptance corresponding to the first mutant;
replacing, upon determining that the probability of acceptance exceeds an acceptance threshold, the quantum program with the first mutant;
storing, upon determining that the quality score exceeds a storage threshold and that the correctness distance is zero, the first mutant in a collection of acceptable mutants; and
terminating, responsive to a number of mutants in the collection of acceptable mutants reaching a threshold number greater than one, the iterating.

2. The method of claim 1 , further comprising:
computing the quality score using an inverse proportionality function on an overall cost.

3. The method of claim 2 , wherein:
cost_diff comprises the overall cost corresponding to the mutant minus an overall cost corresponding to the original program;
the probability of acceptance is one when cost_diff is a negative number; and
the probability of acceptance is e{circumflex over ( )}(-beta*cost_diff) when cost_diff is a positive number, wherein beta comprises a tunable parameter.

4. The method of claim 2 , wherein the overall cost further comprises a correctness cost and a performance cost.

5. The method of claim 1 , further comprising:
computing the probability of acceptance using a direct proportionality function on the quality score.

6. The method of claim 1 , wherein:
quality_diff comprises the quality score corresponding to the mutant minus a quality score corresponding to the original program;
the probability of acceptance is one when quality_diff is a positive number; and
the probability of acceptance is e{circumflex over ( )}(betequality_diff) when quality_diff is a negative number, wherein beta comprises a tunable parameter.

7. The method of claim 1 , further comprising:
terminating the iterating upon determining that the quality score exceeds a storage threshold and that the correctness distance is zero.

8. A computer usable program product comprising a computer-readable storage medium, and program instructions stored on the computer-readable storage medium, the stored program instructions comprising:
program instructions to iterate, until reaching an iteration limit, actions comprising:
program instructions to generate, from a quantum program using a processor and a memory, a first mutant, the first mutant comprising a transformation of the quantum program, wherein the quantum program comprises a set of operations, each operation in the set of operations specifying at least one gate operating on at least one qubit, wherein the transformation comprises inserting, into the set of operations, a synthesized operation comprising an instance of a gate type and at least one qubit on which the instance operates, wherein an insertion point, the gate type, and the at least one qubit of the synthesized operation are randomly selected;
program instructions to compute a quality score, a correctness distance, and a probability of acceptance corresponding to the first mutant;
program instructions to replace, upon determining that the probability of acceptance exceeds an acceptance threshold, the quantum program with the first mutant;
program instructions to store, upon determining that the quality score exceeds a storage threshold and that the correctness distance is zero, the first mutant in a collection of acceptable mutants; and
program instructions to terminate, responsive to a number of mutants in the collection of acceptable mutants reaching a threshold number greater than one, the iterating.

9. The computer usable program product of claim 8 , further comprising:
program instructions to compute the quality score using an inverse proportionality function on an overall cost.

10. The computer usable program product of claim 9 , wherein:
cost_diff comprises the overall cost corresponding to the mutant minus an overall cost corresponding to the original program;
the probability of acceptance is one when cost_diff is a negative number; and
the probability of acceptance is e{circumflex over ( )}(-beta*cost_diff) when cost_diff is a positive number, wherein beta comprises a tunable parameter.

11. The computer usable program product of claim 9 , wherein the overall cost further comprises a correctness cost and a performance cost.

12. The computer usable program product of claim 8 , further comprising:
program instructions to compute the probability of acceptance using a direct proportionality function on the quality score.

13. The computer usable program product of claim 8 , wherein:
quality_diff comprises the quality score corresponding to the mutant minus a quality score corresponding to the original program;
the probability of acceptance is one when quality_diff is a positive number; and
the probability of acceptance is e{circumflex over ( )}(beta*quality_diff) when quality_diff is a negative number, wherein beta comprises a tunable parameter.

14. The computer usable program product of claim 8 , further comprising program instructions to terminate the iterating upon determining that the quality score exceeds a storage threshold and that the correctness distance is zero.

15. The computer usable program product of claim 8 , wherein the stored program instructions are stored in a computer readable storage medium in a data processing system, and wherein the stored program instructions are transferred over a network from a remote data processing system.

16. The computer usable program product of claim 8 , wherein the stored program instructions are stored in a computer readable storage medium in a server data processing system, and wherein the stored program instructions are downloaded over a network to a remote data processing system for use in a computer readable storage medium associated with the remote data processing system.

17. A computer system comprising one or more processors, one or more computer-readable memories, and a computer-readable storage medium, and program instructions stored on the computer-readable storage medium for execution by at least one of the one or more processors via at least one of the one or more memories, the stored program instructions comprising:
program instructions to iterate, until reaching an iteration limit, actions comprising:
program instructions to generate, from a quantum program using a processor and a memory, a first mutant, the first mutant comprising a transformation of the quantum program, wherein the quantum program comprises a set of operations, each operation in the set of operations specifying at least one gate operating on at least one qubit, wherein the transformation comprises inserting, into the set of operations, a synthesized operation comprising an instance of a gate type and at least one qubit on which the instance operates, wherein an inser

Assignees

• IBM

Inventors

• Liu Peng
• Hu Shaohan
• Pistoia Marco
• Chen Richard

Classifications

• G06N10/60

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

• G06N10/80 Primary

  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

• G06N3/126 Primary

  Evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title

• G06F8/443

  Optimisation · CPC title

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title