# qubiter.quantum_CSD_compiler.Tree module¶

class `qubiter.quantum_CSD_compiler.Tree.``Tree`(do_write, file_prefix, emb, init_unitary_mat, verbose=False, **kwargs)[source]

This class creates a binary tree of nodes whose cargo is contained in the attributes of class Node. This class, being a child of class SEO_writer, is also capable of writing English & Picture files. After creating a binary tree, it proceeds to use that tree to produce a CS decomposition of the unitary matrix init_unitary_mat that is fed into its constructor. This CS (cosine-sine) decomp consists of a sequence of diagonal unitaries (DIAG lines in English file) and multiplexors (MP_Y lines in English file) whose product equals init_unitary_mat.

If you wish to expand DIAG and MP_Y lines into cnots and single qubit rotations, use DiagUnitaryExpander and MultiplexorExpander classes.

The CS decomposition was a famous decomp of Linear Algebra well before quantum computing. It was first applied to quantum computing in the 1999 paper and accompanying C++ program cited below. Much of the code of the original C++ Qubiter has been rewritten in Python for the new pythonic Qubiter.

Let init_unitary_mat be N dimensional, with N = 2^n, where n = number of qubits. A general N dimensional unitary matrix has N^2 dofs (real degrees of freedom). That’s because it has N^2 complex entries, so 2*N^2 real parameters, but those parameters are subject to N real constraints and N(N-1)/2 complex constraints, for a total of N^2 real constraints. So 2N^2 real parameters minus N^2 real constraints gives N^2 dofs.

(a) Each DIAG (MP_Y, resp.) line of the CS decomp of init_unitary_mat depends on N (N/2, resp.) angles and there are about N DIAG and N MP_Y lines. So the DIAG lines alone have enough dofs, N^2 of them, to cover all N^2 dofs of init_unitary_mat. So clearly, there is a lot of redundancy in the CS decomp used by Qubiter. But, there is hope: the CS decomp is not unique, and it might be possible to choose a CS decomp that makes zero many of the angles in the DIAG and MP_Y lines. Some of those “compiler optimizations” are considered in references below.

(b) The CS decomp as used here leads to order N^2 = 2^{2n} cnots and qubit rotations so it is impractical for large N. But for small N, it can be useful. For large N, it might be possible to discover approximations to individual MP_Y and DIAG lines. An approximation of this type is considered in MultiplexorExpander.

Clearly, there is much room for future research to improve (a) and (b).

References

1. R.R. Tucci, A Rudimentary Quantum Compiler(2cnd Ed.) https://arxiv.org/abs/quant-ph/9902062

2. Qubiter 1.11, a C++ program whose first version was released together with Ref.1 above. Qubiter 1.11 is included in the quantum_CSD_compiler/LEGACY folder of this newer, pythonic version of Qubiter.

3. R.R. Tucci, Quantum Fast Fourier Transform Viewed as a Special Case of Recursive Application of Cosine-Sine Decomposition, https://arxiv.org/abs/quant-ph/0411097

Variables: global_phase_rads (float) – If arr is the initial unitary matrix fed to the constructor, then this equals delta, where arr = exp(i*delta) arr1, where arr1 is a special unitary matrix (det(arr1) = 1) root_nd (Node) – The root or starting node of the tree. The only node without parents. Each node remembers its children, so you only need the root_nd to access all other nodes.
`__init__`(do_write, file_prefix, emb, init_unitary_mat, verbose=False, **kwargs)[source]

Constructor

Parameters: do_write (bool) – file_prefix (str) – emb (CktEmbedder) – init_unitary_mat (np.ndarray) – This is the matrix that is fed to cs_decomp() in root node constructor. verbose (bool) –
`build_tree`(init_unitary_mat)[source]

This function is called by the constructor to build a tree of Node’s. It returns the root node of the tree.

Parameters: init_unitary_mat (np.ndarray) – Node
`write`()[source]

This function writes English & Picture files. It visits all the Node’s of the tree from right to left (this way: <–). It calls self.write_node() for each node.

Returns: None
`write_node`(nd)[source]

This function is called by self.write() for each node of the tree. For a node with level <= num_bits, the function writes an MP_Y line, whereas if level = num_bits + 1, it writes a DIAG line.

Parameters: nd (Node) – None