Simplified quantum programming

Patent metadata

Field	Value
Publication number	US-11238359-B2
Application number	US-201815874489-A
Country	US
Kind code	B2
Filing date	Jan 18, 2018
Priority date	Jan 18, 2018
Publication date	Feb 1, 2022
Grant date	Feb 1, 2022

Abstract

Techniques facilitating simplified quantum programming are provided. In one example, a computer-implemented method comprises reducing, by a device operatively coupled to a processor, a first computing problem of a problem type to a second computing problem of the problem type, wherein the second computing problem is associated with a quantum circuit; facilitating, by the device, execution of the quantum circuit at a quantum computer, resulting in a first output corresponding to the second computing problem; and mapping, by the device, the first output to a second output corresponding to the first computing problem.

First claim

What is claimed is:

1. A system comprising:
a memory that stores computer executable components; and
a processor that executes the computer executable components stored in the memory, wherein the computer executable components comprise:
a reduction component that reduces, in polynomial time, a first computing problem of a problem type to a second computing problem of the problem type, wherein the first computing problem is a non-3-satisfiability problem that is not executable by a quantum circuit, and the second computing problem a 3-satisfiability problem that is executable by the quantum circuit;
an execution component that facilitates execution of the second computing problem by the quantum circuit at a quantum computer, the execution of the quantum circuit resulting in a second output corresponding to the second computing problem; and
an output mapping component that transforms the second output to a first output corresponding to the first computing problem based on a reduction mapping previously employed to transform a first input set for the first computing problem to a second input set for the second computing problem.

2. The system of claim 1 , wherein the problem type belongs to a class in which respective problems of the class are reducible to each other.

3. The system of claim 2 , wherein the problem type is a nondeterministic polynomial (NP)-complete problem type.

4. The system of claim 1 , wherein the computer executable components further comprise:
an input mapping component that transforms a first input of the first input set to a second input of the second input set based on the reduction mapping, wherein the input mapping component facilitates generation of the second input independently of a level of knowledge of the second computing problem by a user of the system.

5. The system of claim 4 , wherein the computer executable components further comprise:
a construction component that generates configuration data for construction of the quantum circuit by the quantum computer, wherein the quantum circuit comprises an oracle marking subcircuit and an amplitude amplification subcircuit.

6. The system of claim 5 , wherein the construction component generates configuration data for the oracle marking subcircuit by converting respective elements of the second computing problem via at least one of Pauli-X quantum gates or N-th order controlled-not (CNX) quantum gates.

7. The system of claim 6 , wherein the construction component generates configuration data for a CNX quantum gate by combining a number N of controlled-controlled-not (CCX) quantum gates and respectively corresponding ancillary qubits.

8. The system of claim 5 , wherein the construction component generates configuration data for the amplitude amplification subcircuit based on a transformation matrix.

9. The system of claim 1 , further comprising a quantum code generator component that generates a quantum program to solve the 3-satisfiability problem.

10. A computer-implemented method comprising:
reducing, by a device operatively coupled to a processor, in polynomial time, a first computing problem of a problem type to a second computing problem of the problem type, wherein the first computing problem is a non-3-satisfiability problem that is not executable by a quantum circuit, and the second computing problem a 3-satisfiability problem that is executable by the quantum circuit;
facilitating, by the device, execution of the second computing problem by the quantum circuit at a quantum computer, resulting in a second output corresponding to the second computing problem; and
transforming, by the device, the second to a first output corresponding to the first computing problem based on a mapping of a first input set for the first computing problem to a second input set for the second computing problem.

11. The computer-implemented method of claim 10 , wherein the problem type belongs to a class in which respective problems of the class are reducible to each other.

12. The computer-implemented method of claim 10 , further comprising:
transforming, by the device, a first input of the first input set to a second input of the second input set.

13. The computer-implemented method of claim 12 , further comprising:
generating, by the device, configuration data for construction of the quantum circuit by the quantum computer, wherein the quantum circuit comprises an oracle marking subcircuit and an amplitude amplification subcircuit.

14. The computer-implemented method of claim 13 , further comprising:
generating, by the device, configuration data for the oracle marking subcircuit by converting respective elements of the second computing problem via at least one of Pauli-X quantum gates or N-th order controlled-not (CNX) quantum gates.

15. The computer-implemented method of claim 13 , further comprising:
generating, by the device, configuration data for the amplitude amplification subcircuit based on a transformation matrix.

16. The computer-implemented method of claim 10 , further comprising:
generating, by the device, a quantum program to solve the 3-satisfiability problem.

17. A computer program product for facilitating quantum programming, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
reduce, in polynomial time, a first computing problem of a problem type to a second computing problem of the problem type, wherein the first computing problem is a non-3-satisfiability problem that is not executable by a quantum circuit, and the second computing problem a 3-satisfiability problem that is executable by the quantum circuit;
facilitate execution of the second computing problem by the quantum circuit at a quantum computer, resulting in a second output corresponding to the second computing problem; and
map the second to a first output corresponding to the first computing problem based on a mapping of a first input set for the first computing problem to a second input set for the second computing problem.

18. The computer program product of claim 17 , wherein the problem type belongs to a class in which respective problems of the class are reducible to each other.

19. The computer program product of claim 17 , wherein the program instructions further cause the processor to:
transform a first input of the first input set to a second input of the second input set based on the reduction mapping.

20. The computer program product of claim 17 , wherein the program instructions further cause the processor to:
generate a quantum program to solve the 3-satisfiability problem.

Assignees

• IBM

Inventors

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

Classifications

• G06N5/01

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

• G06N10/20

  Models of quantum computing, e.g. quantum circuits or universal quantum computers · 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

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06N5/003

  Physics · mapped topic