Quantum algorithms for arithmetic and function synthesis

Patent metadata

Field	Value
Publication number	US-10320360-B2
Application number	US-201515316500-A
Country	US
Kind code	B2
Filing date	Jun 5, 2015
Priority date	Jun 6, 2014
Publication date	Jun 11, 2019
Grant date	Jun 11, 2019

Abstract

Quantum circuits and associated methods use Repeat-Until-Success (RUS) circuits to perform approximate multiplication and approximate squaring of input values supplied as rotations encoded on ancilla qubits. So-called gearbox and programmable ancilla circuits are coupled to encode even or odd products of input values as a rotation of a target qubit. In other examples, quantum RUS circuits provide target qubit rotations that are associated with reciprocals using series expansion representations.

First claim

The invention claimed is:

1. A quantum circuit, comprising:
a repeat-until-success (RUS) multiplication circuit coupled to a first ancilla qubit and a target qubit at respective RUS multiplication circuit inputs so as to produce, at a target qubit output, a target qubit phase based on a product of a phase coupled to the RUS multiplication circuit at the first ancilla qubit;
a measurement circuit coupled to the first ancilla qubit at an RUS multiplication circuit output; and
a correction circuit coupled to the measurement circuit to apply a correction to the target qubit if the measurement circuit indicates failure.

2. The quantum circuit of claim 1 , wherein the multiplication circuit is a gearbox circuit.

3. The quantum circuit of claim 1 , wherein the multiplication circuit is a PAR circuit.

4. The quantum circuit of claim 1 , wherein a plurality of ancilla qubits are coupled to the RUS multiplication circuit, and the target qubit phase is based on a product of phases supplied to the RUS multiplication circuit associated with the plurality of ancilla qubits.

5. The quantum circuit of claim 4 , wherein the RUS multiplication circuit is a gearbox circuit, and the target qubit phase corresponds to an even power of a product of the phases supplied to the RUS multiplication circuit with the plurality of ancilla qubits.

6. The quantum circuit of claim 4 , wherein the RUS multiplication circuit is a gearbox circuit, and the target qubit phase corresponds to an odd power of a product of the phases supplied to the RUS multiplication circuit with the plurality of ancilla qubits.

7. The quantum circuit of claim 1 , wherein the target qubit phase is associated with a reciprocal.

8. The quantum circuit of claim 7 , wherein the correction circuit includes at least one Clifford gate.

9. At least one computer readable storage device comprising computer executable instructions for a method, comprising:
obtaining a representation of a function of a plurality of variables;
expressing at least a portion of the representation based on at least one product of the plurality of variables; and
assigning at least one repeat-until-success quantum circuit so as to produce a qubit phase corresponding to the at least one product upon success.

10. The at least one computer readable storage device of claim 9 , wherein the method further comprises identifying odd and even powers of the plurality of variables in the portion of the representation, and assigning the at least one repeat-until-success quantum circuit based on the identification.

11. The at least one computer readable storage device of claim 9 , wherein the at least one quantum circuit is a gearbox circuit if an even power is identified or a programmable ancilla rotation (PAR) circuit if an odd power is identified.

12. The at least one computer readable storage device of claim 9 , wherein the at least one quantum circuit is a gearbox circuit or a PAR circuit.

13. The at least one computer readable storage device of claim 9 , wherein method further comprises obtaining an error limit associated with the product, and assigning a plurality of quantum circuits based on the error limit so as to compensate product errors.

14. The at least one computer readable storage device of claim 9 , wherein method further comprises arranging the at least one selected quantum circuit so that the variables of the plurality of variables are coupled to respective ancilla qubits, the target qubit receives the qubit phase based on an error limit associated with the product, and a plurality of quantum circuits is assigned based on the error limit.

15. The at least one computer readable storage device of claim 9 , wherein the method further comprises representing the function as a series of products of the variables.

16. The at least one computer readable storage device of claim 15 , further comprising defining a quantum correction circuit that is coupled to the target qubit and returns the target qubit to an initial state upon failure.

17. The at least one computer readable storage device of claim 15 , wherein values of the variables of the plurality of variables are represented as rotations on respective qubits.

18. The at least one computer readable storage device of claim 9 , wherein the representation of the function includes a least one reciprocal of a variable that is obtained based on a series representation.

19. The at least one computer readable storage device of claim 9 , wherein at least one of the variables is offset so as change an even or odd power term in a series expansion to an odd or even power term, respectively.

20. A method of obtaining a value of a function in quantum computer, comprising:
representing values of a plurality of variables on respective ancilla qubits;
coupling the ancilla qubits to a quantum repeat-until-success circuit that includes at least one gearbox circuit or PAR circuit;
obtaining a corresponding value of the function as a phase on a target qubit if output states of the ancilla qubit correspond to success; and
correcting the phase of the output target qubit upon failure, and coupling the corrected target qubit state to a target qubit input of the quantum repeat-until-success multiplication circuit.

21. The quantum circuit of claim 1 , wherein the product of the phase coupled to the first ancilla qubit is a power of the phase coupled to the first ancilla qubit or a product of the phase coupled to the first ancilla qubit with a second phase that is coupled to a second ancilla qubit.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Wiebe Nathan
• Roetteler Martin

Classifications

• G06F17/17

  Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method ({G06F17/18 takes precedence } ; interpolation for numerical control G05B19/18) · CPC title

• G06N10/00

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

• H03H7/21 Primary

  providing two or more phase shifted output signals, e.g. n-phase output · CPC title

• G06F7/548

  Trigonometric functions; Co-ordinate transformations · CPC title

• G06F7/523

  Multiplying only · CPC title