Method and system for approximate quantum circuit synthesis using quaternion algebra

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.

What is claimed is: 
     
       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 ( U   q   ,R   z (φ))≤ε;  (1) and
 
     nrd ( q )   F =   1   L     1    . . .    M   L     M   ,  (2)
 
 
 
 
       wherein d is a distance function,    1 , . . . ,    M  are the appropriate prime ideals of    F     1   , L 1 , . . . , L M ∈  are their respective multiplicities in the decomposition of nrd(q)   F , and nrd(q) is a reduced norm of a quaternion q. 
     
     
       2. 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. 
 
     
     
       3. The quantum circuit synthesizer system of  claim 1 , wherein the distance function d is
     d =√{square root over (1−| Tr ( U   q   d   R   z (φ))|/2)}.
 
 
     
     
       4. The quantum circuit synthesizer system of  claim 1 , wherein the single qubit gate set is a Clifford+e iπZ/12  basis gate set, a Clifford+e iπ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. 
     
     
       5. 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. 
     
     
       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. 
 
     
     
       7. 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. 
 
     
     
       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. 
 
 
     
     
       9. 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*)=e 1 , where e is an element of the totally real subfield F. 
     
     
       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. 
 
     
     
       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. 
     
     
       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. 
 
     
     
       13. 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.