Quantum algorithms for arithmetic and function synthesis
AssigneeMicrosoft Technology Licensing, LLC
InventorsNathan Wiebe, Martin Roetteler
Life of this patent
Estimating the term…
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.
Claims21
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.
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.
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.
Dependencies are inferred from the claim text.