# US 11,113,084 B2 · Method and system for approximate quantum circuit synthesis using quaternion algebra

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,113,084 B2
- Document ID: US11113084B2
- Status: Granted
- Kind: B2
- Application number: 15/761,836
- Filed: 2016-09-26
- Published: 2018-09-27
- Granted: 2021-09-07
- Earliest claimed: 2015-04-10
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Vadym Kliuchnikov; Jon Yard; Martin Roetteler; Alexei Bocharov
- Web page: https://patentgrep.com/patent/US11113084B2

## CPC

- G06F 9/45508: {Runtime interpretation or emulation, e g. emulator loops, bytecode interpretation}
- G06N 10/20: Models of quantum computing, e.g. quantum circuits or universal quantum computers
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

This application concerns methods, apparatus, and systems for performing quantum circuit synthesis and/or for implementing the synthesis results in a quantum computer system. In certain example embodiments: a universal gate set, a target unitary described by a target angle, and target precision is received (input); a corresponding quaternion approximation of the target unitary is determined; and a quantum circuit corresponding to the quaternion approximation is synthesized, the quantum circuit being over a single qubit gate set, the single qubit gate set being realizable by the given universal gate set for the target quantum computer architecture.

## Claims

### Claim 1

A quantum circuit synthesizer system, comprising:
a processor; and
at least one memory coupled to the processor and having stored thereon processor-executable instructions for a quantum computer synthesis procedure that comprises:
receiving a target unitary described by a target angle and target precision;
determining a corresponding quaternion approximation of the target unitary; and
synthesizing a quantum circuit corresponding to the quaternion approximation, the circuit being over a single qubit gate set, the single qubit gate set being realizable by a target quantum computer architecture, wherein the determining a corresponding quaternion approximation of the target unitary comprises finding a quaternion from an order of a totally definite quaternion algebra defined over a totally real number field F that has the following two properties:
d(Uq,Rz(φ))≤ε; (1) and
nrd(q)F=1L1 . . . MLM, (2)
wherein d is a distance function, 1, . . . , M are the appropriate prime ideals of F1, L1, . . . , LM∈ are their respective multiplicities in the decomposition of nrd(q)F, and nrd(q) is a reduced norm of a quaternion q.

### Claim 2 (depends on 1)

The quantum circuit synthesizer system of claim 1, wherein the synthesis procedure further comprises determining a cost vector for the target unitary, and
wherein the determining the corresponding quaternion approximation comprises finding one or more corresponding quaternion approximations that satisfy the cost vector, wherein the cost vector describes a limit on a size of the single qubit gate set resulting from the synthesis procedure.

### Claim 3 (depends on 1)

The quantum circuit synthesizer system of claim 1, wherein the distance function d is
d=√{square root over (1−|Tr(UqdRz(φ))|/2)}.

### Claim 4 (depends on 1)

The quantum circuit synthesizer system of claim 1, wherein the single qubit gate set is a Clifford+eiπZ/12 basis gate set, a Clifford+eiπZ/16 basis gate set, a V-basis gate set, or any other single qubit base set expressible in terms of totally definite quaternion algebra.

### Claim 5 (depends on 1)

The quantum circuit synthesizer system of claim 1, further comprising a quantum circuit controller coupled to the target quantum circuit architecture and configured to implement the quantum circuit in the target quantum circuit architecture.

### Claim 6

A quantum circuit synthesizer system, comprising:
a processor; and
at least one memory coupled to the processor and having stored thereon processor-executable instructions for a quantum computer synthesis procedure that comprises:
receiving a target unitary described by a target angle and target precision;
determining a corresponding quaternion approximation of the target unitary; and
synthesizing a quantum circuit corresponding to the quaternion approximation, the circuit being over a single qubit gate set, the single qubit gate set being realizable by a target quantum computer architecture, wherein the determining the corresponding quaternion approximation of the target unitary comprises:
selecting a first algebraic integer for use as a first quaternion element in the quaternion approximation, the first algebraic integer being selected so that a distance threshold to a Rx, Ry, or Rz rotation is satisfied.

### Claim 7 (depends on 6)

The quantum circuit synthesizer system of claim 6, wherein the determining the corresponding quaternion approximation of the target unitary further comprises:
selecting a second algebraic integer for use as a second quaternion element in the quaternion approximation, the second algebraic integer being selected so that, in combination with the first algebraic integer, the quaternion approximation produces a quaternion that satisfies a cost limit and the corresponding unitary satisfies the distance threshold.

### Claim 8

A method, comprising:
by a quantum computer synthesis tool adapted for use in a quantum computer design and implementation process and implemented by one or more computing devices:
inputting a program describing a desired computation to be performed in a target quantum computer architecture;
generating a gate set adapted for implementation on the target quantum
computer architecture based on the program, wherein the generating includes generating a single qubit circuit for one or more respective unitaries used to perform the desired computation,
wherein the generating the single qubit circuit comprises:
identifying a target unitary, and
determining a corresponding quaternion approximation of the target unitary using a process in which one or more of the elements in the
corresponding quaternion approximation are randomly selected, wherein the determining the corresponding quaternion approximation of the target unitary comprises:
randomly selecting one or more values for use in the corresponding quaternion approximation from a constrained body of values that guarantees that a norm equation is solvable; and
solving the norm equation to determine at least another one of the elements in the corresponding quaternion approximation.

### Claim 9 (depends on 8)

The method of claim 8, wherein the at least another one of the elements in the corresponding quaternion approximation is z, where z is an algebraic integer from K and wherein the norm equation for Z is Z(Z*)=e1, where e is an element of the totally real subfield F.

### Claim 10

A method, comprising:
by a quantum computer synthesis tool adapted for use in a quantum computer design and implementation process and implemented by one or more computing devices:
inputting a program describing a desired computation to be performed in a target quantum computer architecture;
generating a gate set adapted for implementation on the target quantum
computer architecture based on the program, wherein the generating includes generating a single qubit circuit for one or more respective unitaries used to perform the desired computation,
wherein the generating the single qubit circuit comprises:
identifying a target unitary, and
determining a corresponding quaternion approximation of the target unitary using a process in which one or more of the elements in the
corresponding quaternion approximation are randomly selected, wherein the determining the corresponding quaternion approximation of the target unitary comprises:
randomly sampling points from subsets of a ring of integers; and
using the randomly selected sampling points as quaternion elements in the quaternion approximation.

### Claim 11

A method, comprising:
by a quantum computer synthesis tool adapted for use in a quantum computer design and implementation process and implemented by one or more computing devices:
inputting a program describing a desired computation to be performed in a target quantum computer architecture;
generating a gate set adapted for implementation on the target quantum
computer architecture based on the program, wherein the generating includes generating a single qubit circuit for one or more respective unitaries used to perform the desired computation,
wherein the generating the single qubit circuit comprises:
identifying a target unitary, and
determining a corresponding quaternion approximation of the target unitary using a process in which one or more of the elements in the corresponding quaternion approximation are randomly selected, wherein the determining the corresponding quaternion approximation of the target comprises:
partitioning a convex body of complex numbers into convex subsets, the partitioning being
performed such that each subset has a lattice point corresponding to K;
randomly selecting one of the subsets;
selecting a lattice point corresponding to K from the randomly selected subset; and
using the selected lattice point as an element in the quaternion approximation.

### Claim 12

One or more computer-readable memory or storage devices storing computer-executable instructions which when executed by a computer cause the computer to perform a quantum computer synthesis procedure comprising:
receiving a target unitary described by a target angle and target precision; determining a corresponding quaternion approximation of the target unitary; synthesizing the corresponding quaternion approximation to produce a single qubit circuit for the target unitary, the single qubit circuit being realizable by a quantum computer architecture,
wherein the determining the corresponding quaternion approximation of the target unitary uses a Closest Vector Problem (CVP) technique to select values for the corresponding quaternion approximation.

### Claim 13 (depends on 12)

The one or more computer-readable memory or storage devices of claim 12, wherein the determining the corresponding quaternion approximation of the target unitary comprises selecting values from a size-reduced basis as an element in the corresponding quaternion approximation.