Problem of universality in simulation of evolution of quantum system and in theory of quantum computations related with possibility of expression or approximation of arbitrary unitary transformation by composition of specific unitary transformations (quantum gates) from given set. In earlier paper (quant-ph/0010071) was shown application of Clifford algebras to constructions of universal sets of binary quantum gates
UkinU(2n). For application of similar approach to non-binary quantum gates
UkinU(ln) in present work is used rational noncommutative torus
BbbT1/l2n. Set of universal non-binary two-gates is presented here as one of examples.
A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in
NP∩BQP and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at
k=1, recovering the repetition number contains finite-field discrete logarithm over
F2r×. In general, restricting every exponent to
{0,1} removes the Abelian-group closure and makes feasibility NP-complete for variable
k, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.
We address the problem of universality in simulation of evolution of quantum system and in theory of quantum computations related with the possibility of expression or approximation of arbitrary unitary transformation by composition of specific unitary transformations (quantum gates) from given set. In an earlier paper application of Clifford algebras to constructions of universal sets of binary quantum gates Uk∈U(2n) was shown. For application of a similar approach to nonbinary quantum gates Uk∈U(ln), in present work we used rational noncommutative torus T1/l2n. A set of universal nonbinary two-gates is presented here as one example.
The Clifford hierarchy of unitary operators is a foundational concept for universal quantum computation. It was introduced to show that universal quantum computation can be realized via quantum teleportation, given access to certain standard resources. While the full structure of the hierarchy is still not understood, Cui et al. [S. X. Cui et al., Phys. Rev. A 95, 012329 (2017)] recently described the structure of diagonal unitaries in the hierarchy. They considered diagonal unitaries whose action on a computational basis qudit state is described by a
2kth root of unity raised to some polynomial function of the state, and they established the level of such unitaries in the hierarchy as a function of
k and the degree of the polynomial. For qubit systems, we consider
kth-level diagonal unitaries that can be described just by quadratic forms of the state over the ring
Z2k of integers modulo
2k. The quadratic forms involve symmetric matrices over
Z2k that can be used to efficiently describe all two-local and certain higher locality diagonal gates in the hierarchy. We also provide explicit algebraic descriptions of their action on Pauli matrices, which establishes a natural recursion to diagonal unitaries from lower levels. The result involves symplectic matrices over
Z2k and hence our perspective unifies a subgroup of diagonal gates in the Clifford hierarchy with the binary symplectic framework for gates in the Clifford group. We augment our description with simple examples for certain standard gates. In addition to demonstrating structure, these formulas might prove useful in applications such as (i) classical simulation of quantum circuits, especially via the stabilizer rank approach, (ii) synthesis of logical non-Clifford unitaries, specifically alternatives to expensive magic state distillation, and (iii) decomposition of arbitrary unitaries beyond the
Clifford+T set of gates, perhaps leading to shorter depth circuits. Our results suggest that some nondiagonal gates in the hierarchy might also be understood by generalizing other binary symplectic matrices to integer rings.
Clifford algebras are used for definition of spinors. Because of using spin-1/2 systems as an adequate model of quantum bit, a relation of the algebras with quantum information science has physical reasons. But there are simple mathematical properties of the algebras those also justifies such applications. First, any complex Clifford algebra with 2n generators, Cl(2n,C), has representation as algebra of all 2^n x 2^n complex matrices and so includes unitary matrix of any quantum n-gate. An arbitrary element of whole algebra corresponds to general form of linear complex transformation. The last property is also useful because linear operators are not necessary should be unitary if they used for description of restriction of some unitary operator to subspace. The second advantage is simple algebraic structure of Cl(2n) that can be expressed via tenzor product of standard "building units" and similar with behavior of composite quantum systems. The compact notation with 2n generators also can be used in software for modeling of simple quantum circuits by modern conventional computers.