In fault-tolerant quantum computation and quan-tum error-correction one is interested on Pauli matrices that commute with a circuit/unitary. This information is encoded by the support (Pllaha et al., 2020) of the given circuit/unitary. We provide a fast algorithm that decomposes any Clifford gate as a minimal product of Clifford transvections. The algorithm can be directly used for computing the support of any given Clifford gate. To achieve this goal, we exploit the structure of the symplectic group with a novel graphical approach.
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.
Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.
The Clifford hierarchy is a nested sequence of sets of quantum gates critical to achieving fault-tolerant quantum computation. Diagonal gates of the Clifford hierarchy and ‘nearly diagonal’ semi-Clifford gates are particularly important: they admit efficient gate teleportation protocols that implement these gates with fewer ancillary quantum resources such as magic states. Despite the practical importance of these sets of gates, many questions about their structure remain open; this is especially true in the higher-dimensional qudit setting. Our contribution is to leverage the discrete Stone–von Neumann theorem and the symplectic formalism of qudit stabilizer theory towards extending the results of Zeng et al . (2008) and Beigi & Shor (2010) to higher dimensions in a uniform manner. We further give a simple algorithm for recursively enumerating all gates of the Clifford hierarchy, a simple algorithm for recognizing and diagonalizing semi-Clifford gates, and a concise proof of the classification of the diagonal Clifford hierarchy gates due to Cui et al . (2016) for the single-qudit case. We generalize the efficient gate teleportation protocols of semi-Clifford gates to the qudit setting and prove that every third-level gate of one qudit (of any prime dimension) and of two qutrits can be implemented efficiently. Numerical evidence gathered via the aforementioned algorithms supports the conjecture that higher-level gates can be implemented efficiently.
Decomposing unitary operators into Clifford gates and non-Clifford gates is an extremely important problem in quantum computing, as each extra quantum gate in a quantum circuit makes it more prone to errors. The first objective in this problem is usually to minimize the number of non-Clifford gates. The second objective, and the objective of this thesis, is to minimize the number of 2-qubit gates in the Clifford operators that are left. Most algorithms from the literature for decomposing Clifford operators into Clifford gates involve using a decomposition such as the Bruhat decomposition to first split the input operator into multiple separate operators. These operators are then individually decomposed into Clifford gates. A problem with this approach is that the minimum number of 2-qubit gates needed to implement all the separate operators can be greater than what is needed to implement the input Clifford operator in the first place. This thesis tackles this problem by developing an algorithm for decomposing Clifford operators into Clifford gates without splitting the input operator into multiple smaller operators first. To help with the decomposition steps, this thesis defines a set of operators called 2-qubit symplectic transvections. This results in an algorithm that performs well for small to medium sized Clifford operators. This thesis assumes that the order of the qubits does not affect the implementation cost for quantum gates. This means that swap gates can be implemented for free by relabeling the qubits. It is also assumed that 1-qubit gates have negligible implementation cost compared to 2-qubit gates.
The stabiliser formalism plays a central role in quantum computing, error correction, and fault tolerance. Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of many classical algorithms in quantum information, e.g. for gate synthesis, circuit optimisation, and simulating quantum circuits. These core functions are also used in the numerical experiments critical to formulating and testing mathematical conjectures on the stabiliser formalism.We develop novel mathematical insights concerning stabiliser states and Clifford gates that significantly clarify their descriptions. We then utilise these to provide ten new fast algorithms which offer asymptotic advantages over any existing implementations. We show how to rapidly verify that a vector is a stabiliser state, and interconvert between its specification as amplitudes, a quadratic form, and a check matrix. These methods are leveraged to rapidly check if a given unitary matrix is a Clifford gate and to interconvert between the matrix of a Clifford gate and its compact specification as a stabiliser tableau.For example, we extract the stabiliser tableau of a 2n×2n matrix, promised to be a Clifford gate, in O(n2n) time. Remarkably, it is not necessary to read all the elements of a Clifford gate matrix to extract its stabiliser tableau. This is an asymptotic speedup over the best-known method that is exponential in the number of qubits.We provide implementations of our algorithms in Python and C++ that exhibit vastly improved practical performance over existing algorithms in the cases where they exist.