Monte carlo markov chain based quantum program optimization

Patent metadata

Field	Value
Publication number	US-2020042882-A1
Application number	US-201816052348-A
Country	US
Kind code	A1
Filing date	Aug 1, 2018
Priority date	Aug 1, 2018
Publication date	Feb 6, 2020
Grant date	—

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 randomly-generated transformation of the quantum program;
computing a quality score, a correctness distance, and a probability of acceptance corresponding to the first mutant;
determining, according to the probability of acceptance, an acceptance corresponding to the first mutant;
replacing, upon determining that an acceptance of the first mutant corresponding to the probability of acceptance exceeds an acceptance threshold, the quantum program with the first mutant; and
storing, upon determining that the quality score exceeds a storage threshold and that the correctness distance is zero, the first mutant.

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 the 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 ê (-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 the 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 ê (beta*quality_diff) when quality_diff is a negative number, wherein beta comprises a tunable parameter.

7 . The method of claim 1 , further comprising:
terminating the iteration upon the numbered of stored mutants exceeding a threshold.

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

9 . A computer usable program product comprising one or more computer-readable storage devices, and program instructions stored on at least one of the one or more storage devices, 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 randomly-generated transformation of the quantum program;
program instructions to compute a quality score, a correctness distance, and a probability of acceptance corresponding to the first mutant;
program instructions to determine, according to the probability of acceptance, an acceptance corresponding to the first mutant;
program instructions to replace, upon determining that an acceptance of the first mutant corresponding to the probability of acceptance exceeds an acceptance threshold, the quantum program with the first mutant; and
program instructions to store, upon determining that the quality score exceeds a storage threshold and that the correctness distance is zero, the first mutant.

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

11 . The computer usable program product of claim 10 , wherein:
cost_diff comprises the overall cost corresponding to the mutant minus the 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 ê (-beta*cost_diff) when cost_diff is a positive number, wherein beta comprises a tunable parameter.

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

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

14 . The computer usable program product of claim 9 , wherein: quality_diff comprises the quality score corresponding to the mutant minus the 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 ê (beta*quality_diff) when quality_diff is a negative number, wherein beta comprises a tunable parameter.

15 . The computer usable program product of claim 9 , further comprising program instructions to terminate the iteration upon the numbered of stored mutants exceeding a threshold.

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

17 . The computer usable program product of claim 9 , wherein the computer usable code is stored in a computer readable storage device in a data processing system, and wherein the computer usable code is transferred over a network from a remote data processing system.

18 . The computer usable program product of claim 9 , wherein the computer usable code is stored in a computer readable storage device in a server data processing system, and wherein the computer usable code is downloaded over a network to a remote data processing system for use in a computer readable storage device associated with the remote data processing system.

19 . A computer system comprising one or more processors, one or more computer-readable memories, and one or more computer-readable storage devices, and program instructions stored on at least one of the one or more storage devices 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 randomly-generated transformation of the quantum program;
program instructions to compute a quality score, a correctness distance, and a probability of acceptance corresponding to the first mutant;
program instructions to determine, according to the probability of acceptance, an acceptance corresponding to the first mutant;
program instructions to replace, upon determining that an acceptance of the first mutant corresponding to the probability of acceptance exceeds an acceptance threshold, the quantum program with the first mutant; and
program instructions to store, upon determining that the quality score exceeds a storage threshold and that the correctness distance is zero, the first mutant.

20 . The computer system of claim 19 , further comprising:
program instructions to compute the quality score using an inverse proportionality function on an overall cost.

Assignees

• IBM

Inventors

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

Classifications

• G06N3/126 Primary

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

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · 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

• G06N99/002

  Physics · mapped topic