Mutual transformations of arbitrary ternary qubit trees by Clifford gates
Alexander Yu. Vlasov


Dimensional Crossover of Microscopic Magnetic Metasurfaces for Magnetic Field Amplification
    A. V. Silhanek
    April 29, 2024
===========================================================================================




 It is shown that ternary qubit trees with the same number of
 nodes can be transformed by the naturally defined sequence of 
 Clifford gates into each other or into standard representation 
 as 1D chain corresponding to Jordan-Wigner transform.




§ INTRODUCTION

 

The ternary qubit tree <cit.> is a visual representation for a generalization of 
Jordan-Wigner transform <cit.> from a set of operators naturally defined for 1D chain. 
The particular case of full ternary tree was suggested for optimal fermion-to-qubit mapping 
in quantum computations <cit.> and similar idea can be applied to more general ternary trees 
<cit.>. 

Qubit trees provide a method to construct set of operators with necessary commutation 
properties, however for some applications it would be desirable also to provide a map
for conversion to standard Jordan-Wigner transform. The algorithm for representation 
of such map as a sequence of so-called stabilizer or Clifford gates <cit.> is 
presented in this work. 

The definition of ternary qubit trees and relation with Jordan-Wigner transform
are recollected in Clif. The sequence of transformations of such
trees producing necessary stabilizer circuit is discussed in Trans.
Possible applications are briefly outlined in last section.




§ CLIFFORD ALGEBRAS AND QUBIT TREES



Let us recollect definition of Clifford algebra <cit.> (n) generated by 
n elements with properties

    _j _k + _k _j = 2 δ_jk,   j,k=1,…,n,
 
where  is unit of the algebra. Often right side of ClAl includes 
minus sign <cit.>, but for complex Clifford algebra considered here such 
change is not essential due to possibility to multiply generators on imaginary unit.
The Clifford algebras defined here should not be confused with Clifford gates
also used in presented work.
The generators ClAl can be expressed using tensor product of Pauli matrices

    σ^x = [ 0 1; 1 0 ],  σ^y = [ 0 -;   0 ],  σ^z = [  1  0;  0 -1 ].
  
For even n=2m such representation corresponds to Jordan-Wigner transform <cit.>

    [                      _2k-1                          = σ^z⊗⋯⊗σ^z_k-1 ⊗σ^x⊗⊗⋯⊗_m-k;                        _2k                          = σ^z⊗⋯⊗σ^z_k-1 ⊗σ^y⊗⊗⋯⊗_m-k ],     k=1,…,m.
 
It can be rewritten

    _2k-1 = (∏_j=1^k-1σ_j^z)σ_k^x ,     _2k = (∏_j=1^k-1σ_j^z)σ_k^y,
         k=1,…,m.

using formal notation

    σ_k^ν = ⊗⋯⊗_k-1 ⊗σ^ν⊗⊗⋯⊗_m-k,   
    k=1,…,m,  ν = x,y,z.

corresponding to action of Pauli matrix on a qubit with index k.


Due to ClAl the basis of Clifford algebra is 2^n different products of 
generators _j and for n=2m due to ClGen it coincides with 2^2m=4^m 
different tensor products of m Pauli matrices. The ClGen is not unique
representation of elements with property ClAl as tensor product of Pauli matrices.

Let us recollect big class of alternative representations with so-called ternary qubit 
trees <cit.>. Such trees have m qubit nodes joined with three children by 
directed links marked by indexes x,y,z and 2m+1 terminal nodes. An example of full ternary tree
of such kind is represented on tern_tree, but arbitrary tree with up to three children 
nodes could be augmented to such ternary tree by attaching missing terminal nodes. An example of
such ternary tree constructed from a binary one is shown on bin_tree.





 

Let us now associate σ_k^ν with a link from qubit k with a mark ν.
Then each path P from a root to a terminal node corresponds to product along this path

    _P = ∏_Pσ_k(P)^ν(P).

Any two such products _P and _P' include only one Pauli matrix with the same k
and different ν≠ν'. Here k is an index of last qubit in common part of paths P and P' 
before forking. Thus, any two unequal products e33 anticommute and satisfy `nontrivial
part' _j_k=-_k_j, j ≠ k of ClAl. The `trivial part' _j^2= is 
also obviously satisfied.


For example full ternary tree on tern_tree corresponds to 27 products

    _1 = σ^x_1σ^x_2σ^x_5, 
     _2 = σ^x_1σ^x_2σ^y_5, 
     _3 = σ^x_1σ^x_2σ^z_5,
     _4 = σ^x_1σ^y_2σ^x_6, …,
     _27 = σ^z_1σ^z_4σ^z_13
 
and binary tree on bin_tree produces seven generators 

    _1 = σ_1^z,
     _2 = σ_1^xσ_2^z,
     _3 = σ_1^yσ_3^z,
     _4 = σ_1^xσ_2^x,
     _5 = σ_1^xσ_2^y,
     _6 = σ_1^yσ_3^x,
     _7 = σ_1^yσ_3^y.



There are 2m+1 such products corresponding to number of terminal nodes, but arbitrary one 
can be dropped, because up to unessential “phase” any such _P can be represented as 
product of other 2m terms <cit.>.
For usual Jordan-Wigner transform ClGen the extra term would correspond to  

    _2m+1 = ∏_j=1^kσ_j^z.





§ TRANSFORMATIONS BETWEEN REPRESENTATIONS



For any unitary operator U adjoint action (conjugation by U) produces new 
set of generators 
    Ad_U _j ↦ U _j U^-1 = U _j U^†,   j=1,…,n

satisfying necessary commutation relation ClAl. For U represented by
so-called quantum stabiliser circuits composed from product of Clifford 
gates <cit.> TranGen represent transformation 
between 4^k different products of σ_k^ν sigk. Such a property was 
discussed earlier for application to construction of new quantum gates effectively
modelled by classical computer <cit.>.

Let us recollect construction of Clifford (stabilizer) gates <cit.>. 
For a single qubit the group transforming σ^ν into each other by conjugation 
may be generated by Pauli matrices σ^ν together with Hadamard matrix H and
`phase gate' S

    H = [  1  1;  1 -1 ], 
        S = [ 1 0; 0   ].

Conjugation by Pauli matrices can only change a sign and neglected further, 
but H and S exchanges σ_x ↔σ_z
and σ_x ↔σ_y respectively.

For two qubits together with  
H_j and S_j, j=1,2 acting on any of them it is necessary to include two-qubit gate 
Controlled-NOT (CX) or Controlled-Z (CZ) to generate whole group of stabilizer 
transformations

    CX = [ 1 0 0 0; 0 1 0 0; 0 0 0 1; 0 0 1 0 ],    
     CZ = [  1  0  0  0;  0  1  0  0;  0  0  1  0;  0  0  0 -1 ].

For arbitrary number of qubits compositions of gates H_j, S_j acting on arbitrary
qubit j together with CX_jk or CZ_jk acting on arbitrary pair of qubits (j, k)
generate whole group of transformations preserving products σ_k^ν (and
basis of Clifford algebra). 

The exchange between arbitrary pair of qubits also may be
decomposed on such operators, but for convenience it should be included as a separate gate.
The operator CZ_jk is used further due to convenience for some transformations of 
qubit trees, symmetry of two indexes and commutativity for different qubits. 

Conjugation by CZ_12 for all possible tensor products of Pauli (and 
identity) matrices are collected in the table below

    [               ⊗ →⊗     σ_x ⊗→σ_x ⊗σ_z     σ_y ⊗→σ_y ⊗σ_z        σ_z ⊗→σ_z ⊗;     ⊗σ_x →σ_z ⊗σ_x σ_x ⊗σ_x →σ_y ⊗σ_y σ_y ⊗σ_x →σ_x ⊗σ_y     σ_z ⊗σ_x →⊗σ_x;     ⊗σ_y →σ_z ⊗σ_y σ_x ⊗σ_y →σ_y ⊗σ_x σ_y ⊗σ_y →σ_x ⊗σ_x     σ_z ⊗σ_y →⊗σ_y;         ⊗σ_z →⊗σ_z     σ_x ⊗σ_z →⊗σ_z     σ_y ⊗σ_z →⊗σ_z σ_z ⊗σ_z →σ_z ⊗σ_z;                    ]


Let us consider action of stabiliser gates on the qubit trees.
The one-qubit gates such as H_j, S_j and products of such operators
map one qubit tree into another and simply exchange labels x,y,z of links 
attached to qubit j. For system with two qubits any set of generators
may be represented as ternary tree and so two qubit-gates CZ
also corresponds to some transformation of the trees. 

For three and more qubits two-qubit gates such as CZ_jk may 
transform products representing _j for some ternary qubit tree into collection
that either represent another tree or not. For example let us consider
standard six generators ClAl for three qubits

    _1 = σ^x_1, _2 = σ^y_1,
      _3 = σ^z_1σ^x_2, _4 = σ_z^1σ^y_2,
      _5 = σ^z_1σ^z_2σ^x_3, _6 = σ^z_1σ^z_2σ^y_3.

Conjugation by U = CZ_12 CZ_23 produces six generators
mentioned in Ref. <cit.>
with correct commutation relation ClAl, but without representation
as a ternary qubit tree

    _1 = σ^x_1σ^z_2, _2 = σ^y_1σ^z_2,
      _3 = σ^x_2σ^z_3, _4 = σ^y_2σ^z_3,
      _5 = σ^z_1σ^x_3, _6 = σ^z_1σ^y_3.



Anyway, CZ_jk also may produce valid transformation of ternary tree
and it is shown further, how it is possible to map any ternary tree
T into standard (Jordan-Wigner) form corresponding to ClGen using 
TranGen with some operator denoted here as U_T^† with the inverse 
transformation U_T mapping ClGen into set of generators for T. 
Arbitrary tree T also can be converted into another 
T' by composition of two such transformations U_T^† U_T' with possible 
further optimization to reduce number of gates. 


The idea is to `straighten all forks' in the tree. Let us consider
last fork on one of the branches originated from some qubit
with index q_1. It is depicted on trans_treea.
It is supposed, that there are no more forks on the branches
attached to the qubit q_1, but this branches can be either terminal
or include arbitrary number of qubit nodes. For certainty the 
branch attached by link with mark x has maximal amount of nodes.



 

Let us show that conjugation by gate CZ_q_1q_2 rejoins the closest qubit 
node with index q_1 to the link marked by y, see trans_treeb. 
Here we suppose that node q_2 has two
terminal nodes attached by links x and y with some tree T_1 may be 
attached to link z. It is always possible to exchange marks 
in such a way by one-qubit transformation. Some trees T_2 and
T_3 also may be attached to qubit node q_1 by links
with marks y and z.



The scheme of tensor products of Pauli (and identity) matrices for generators corresponding
to ternary qubit tree on trans_treea is presented on the left-hand side
of forks.

    [     ⋯ σ^x ⊗σ^x ⊗ ⋯ ⋯;     ⋯ σ^x ⊗σ^y ⊗ ⋯ ⋯; ⋯ σ^x ⊗σ^z ⊗ T_1 ⋯ ⋯;    ⋯ σ^y ⊗  ⊗⋯ T_2 ⋯;     ⋯ σ^z ⊗  ⊗⋯⋯ T_3;                      ]  ⟶  [    ⋯ σ^y ⊗σ^y ⊗ ⋯ ⋯;    ⋯ σ^y ⊗σ^x ⊗ ⋯ ⋯;  ⋯ σ^x ⊗  ⊗ T_1 ⋯ ⋯; ⋯ σ^y ⊗σ^z ⊗⋯ T_2 ⋯;    ⋯ σ^z ⊗  ⊗⋯⋯ T_3;                     ]

Here non-overlapping commuting terms T_1, T_2, T_3 correspond
to subtrees on trans_tree. They could be arbitrary, yet only
subtrees without forks are enough further. The positions corresponding to 
qubits q_1 and q_2 for simplicity are arranged sequentially
in forks and corresponds to combinations

    σ^x ⊗σ^x,  σ^x ⊗σ^y,
      σ^x ⊗σ^z,   σ^y ⊗,
      σ^z ⊗

mapping due to CZmap into

    σ^y ⊗σ^y,  σ^y ⊗σ^x,
       σ^x ⊗,  σ^y ⊗σ_z,
      σ^z ⊗

respectively. The result of such map is shown on the right-hand side of forks
and corresponds to qubit tree on trans_treeb.




Example of conversions from a triple fork to a linear chain is shown on trees7x6. 
Three branches with two nodes are attached to qubit q_1 by x, y and z links on 
trees7x6a. 
The gate CZ_12 is used to move one qubit node from x to y branch,  
see trees7x6b. The gate CZ_13 moves yet another qubit node from x to y and on 
trees7x6c now the x branch has a single terminal node. To continue process it
is necessary to exchange branches x and z by gate H_1, see trees7x6d.
Now it is possible to move qubit nodes q_6 and q_7 from x to y branch
using gates CZ_16 and CZ_17,  see trees7x6e.
Now only y-branch has qubit nodes and gates S_1 and H_1 are used
finally to exchange y and z links to produce a chain of z-linked nodes, 
see trees7x6f.

Consequent application of similar operations to all forks on a ternary qubit tree produces
chain without any branches with nodes connected by z-links. It is only necessary
to rearrange qubit indexes in ascending order to produce `degenerate' qubit tree
corresponding to a chain and standard (Jordan-Wigner) representation ClGen
of generators _j.




§ CONCLUSION



Adjoint map TranGen between standard Jordan-Wigner transform ClGen and 
representation by arbitrary ternary qubit tree e33 using stabilizer circuits,
i.e., sequence of Clifford gates is constructed 
in this work. The applications of such map can be numerous. A general idea
of a few such applications is similar with mentioned in Ref. <cit.> for 
some other examples of quantum circuits `intertwined by Clifford operations'.

It was initially suggested for effective simulations of specific nonuniversal quantum 
circuits by classical computer, but some ideas recollected below can be useful
for other applications.

The approach with conjugation by Clifford operations also looks more general, 
because not all set of generators expressed as TranGen can be represented 
by ternary trees.
However, such ideas appropriate for any set of generators represented
using conjugation TranGen and so may be applied to ternary trees as well
due to construction discussed in Trans.

Adjoint transformation G'=Ad_U G can be associated 
with transition from a quantum circuit G acting on a state |Ψ⟩ to a new circuit
G' for a quantum state |Ψ'⟩ = U |Ψ⟩ with trivial substitution

    G'|Ψ'⟩ = UGU^†|Ψ'⟩ =  UGU^† U |Ψ⟩ = U G |Ψ⟩.
 

Any observable O used
in the measurement ⟨Ψ|O|Ψ⟩ for some states in initial circuit 
would correspond to new observable O' = U O U^†. 
If such observables was expressed  
as an analytical function of generators _k, e.g., quadratic, polynomial
or exponential, the new observables also can be expressed in the same way.
Similar property also valid for Hamiltonians H used for formal expression
of quantum evolution 

    |Ψ(t)⟩ = G|Ψ⟩ = exp(- H t)|Ψ⟩,
 
i.e., for new quantum system or circuit a Hamiltonian can be 
expressed as H' = U H U^†. 
Here the general ideas of possible applications are only outlined
and concrete examples should be discussed elsewhere.

10
	
	
	VlaQ3 A. Yu. Vlasov, “Clifford algebras, Spin groups and qubit trees,”
	arXiv:1904.09912 [quant-ph] (2019); Quanta  11 97–114 (2022).
	JW P. Jordan and E. Wigner,
	“Über das Paulische  Äquivalenzverbot,” 
	Zeitschrift für Physik 47, 631–651 (1928).
	JKMN Z. Jiang, A. Kalev, W. Mruczkiewicz, and H. Neven, “Optimal fermion-to-qubit mapping 
	via ternary trees with applications to reduced quantum states learning,” 
	arXiv:1910.10746 [quant-ph] (2019);
	Quantum 4, 276 (2020).
	VQE J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, 
	I. Rungger, G. H. Booth, and J. Tennyson, “The variational quantum eigensolver: a review of methods
	and best practices,” arXiv:2111.05176 [quant-ph] (2021); Phys. Rep. 986, 1–128 (2022).
	bonz A. Miller, Z. Zimborás, S. Knecht, S. Maniscalco, and G. García-Pérez, 
	“Bonsai algorithm: Grow your own fermion-to-qubit mappings,” 
    arXiv:2212.09731 [quant-ph] (2022); PRX Quantum 4 030314 (2023).
    Gott97 D. Gottesman, “Theory of fault-tolerant quantum computation,” 
    quant-ph/9702029 (1997);  57, 127–137 (1998).
    NCQC M. Nielsen and I. Chuang, Quantum Computation and Quantum Information
    (CUP, Cambridge, 2011).   
	ClDir J. E. Gilbert and M. A. M. Murray, 
	Clifford Algebras and Dirac Operators in Harmonic Analysis
	(CUP, Cambridge, 1991).
	JM8 R. Jozsa and A. Miyake, 
	“Matchgates and classical simulation of quantum circuits,”
	arXiv:0804.4050 [quant-ph];
	Proc. R. Soc. London, Ser. A 464, 3089–3106 (2008). 	
 

