Skip to content

Computes an efficient quantum algorithm for the quantum Schur transform on n qubits.

Notifications You must be signed in to change notification settings

erabinov/schur-transform

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

31 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

README for schur-transform

Computes an efficient quantum algorithm for the quantum Schur transform on $n$ qubits.

The quantum algorithm is returned as a list of $O(n^3)$ two-level operations in matrix form. These could each be decomposed into $O(n\log(n/\epsilon))$ Clifford+T operators using a universal unitary decomposition algorithm such as given in arXiv:1306.3200, for a total operation count of $O(n^4\log(n/\epsilon))$ and overall error bounded by $\epsilon$.

The quantum algorithm uses $2\lfloor\log_2(n)\rfloor-1$ ancillary qubits for a total register of $n+2\lfloor\log_2(n)\rfloor-1$ qubits. The Schur transform maps the standard computational basis to a basis composed of a direct sum of irreducible modules for the unitary and symmetric groups. Equivalently, it maps individual spin eigenvectors to eigenvectors of the composite spin for the whole register.

We assume that the initial register written as a vector has form $$(\text{ancillary qubits})\otimes(\text{computational qubits})$$. The output vector will be organized by subspaces with distinct values of composite total spin. An auxiliary algorithm to calculate the locations of the output states is provided.

Python implementation

Runs with Python 3.2+.

The main procedure in "schurtransform.py" is schuralg(n), which returns a list of $O(n^3)$ elements with form $entry_i=[t_i,R_i,b_i]$. Each $R_i$ is a one- or two-level rotation such that $\prod_i\textbf{I}{2^{t_i}}\otimes R_i\otimes\textbf{I}{2^{b_i}}$ gives the Schur transform ($\textbf{I}_d$ is the identity matrix of dimension $d$).

schurindices(n) returns a dict that maps the key '$s,k,m_s$' to the output entry used to encode the state with spin-projection $m_s$ in the $k$th copy of the spin-$s$ subspace.

For example, $$\textit{schurindices(n)}(3)[\text{`}3/2,1,1/2\text{'}]$$ will return $2$, the index of the state with spin-projection $1/2$ in the $1$st copy of the spin-$3/2$ subspace.

Mathematica implementation

This version allows straightforward interactive visualization using Mathematica language tools.

Runs with Mathematica 10+.

The main procedure in "Schur Transform.nb" is SchurDecomp[n], which returns a list of $O(n^3)$ elements with form $entry_i={t_i,R_i,b_i}$. Each $R_i$ is a one- or two-level rotation such that $\prod_i\textbf{I}{2^{t_i}}\otimes R_i\otimes\textbf{I}{2^{b_i}}$ gives the Schur transform ($\textbf{I}_d$ is the identity matrix of dimension $d$).

SchurIndices[n] returns an association (map) that takes the key ${s,k,m_s}$ to the output entry used to encode the state with spin-projection $m_s$ in the $k$th copy of the spin-$s$ subspace. For example, $$\textbf{SchurIndices}[3][{3/2,1,1/2}]$$ will return $2$, the index of the state with spin-projection $1/2$ in the $1$st copy of the spin-$3/2$ subspace.

About

Computes an efficient quantum algorithm for the quantum Schur transform on n qubits.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Mathematica 89.0%
  • Python 11.0%