We propose a mathematical framework that we call quantum, higher-order Fourier analysis. This generalizes the classical theory of higher-order Fourier analysis, which led to many recent advances in number theory and combinatorics. We define a family of "quantum measures" on linear transformations on a Hilbert space, that reduce in the case of diagonal matrices to the uniformity norms introduced by Timothy Gowers. We show that our quantum measures and our related theory of quantum higher-order Fourier analysis characterize the Clifford hierarchy, an important notion of complexity in quantum computation. In particular, we give a necessary and sufficient analytic condition that a unitary is an element of the [Formula: see text] level of the Clifford hierarchy.
The Clifford hierarchy plays a central role in fault-tolerant quantum computation, but its higher levels remain only partially understood. Recent work on quantum higher order Fourier analysis characterizes membership in the Clifford hierarchy using quantum derivatives, but does not provide an explicit description of the individual levels. In this work, we address this problem by showing that the collection of quantum derivatives of a unitary operator forms a non-abelian
1-cocycle, and conversely that every such
1-cocycle arises from a unitary operator. This yields a recursive cohomological characterization of the Clifford hierarchy. We then specialize this framework to the third level and decompose the cocycle data into symplectic, affine, and phase components, each admitting a cohomological interpretation. As applications, we give a new proof that every two-qudit gate in the third level of the Clifford hierarchy is semi-Clifford, and prove for the first time that every three-qudit gate in the third level is semi-Clifford.
Higher-order quantum theory is an extension of quantum theory where one introduces transformations whose input and output are transformations, thus generalizing the notion of channels and quantum operations. The generalization then goes recursively, with the construction of a full hierarchy of maps of increasingly higher order. The analysis of special cases already showed that higher-order quantum functions exhibit features that cannot be tracked down to the usual circuits, such as indefinite causal structures, providing provable advantages over circuital maps. The present treatment provides a general framework where this kind of analysis can be carried out in full generality. The hierarchy of higher-order quantum maps is introduced axiomatically with a formulation based on the language of types of transformations. Complete positivity of higher-order maps is derived from the general admissibility conditions instead of being postulated as in previous approaches. The recursive characterization of convex sets of maps of a given type is used to prove equivalence relations between different types. The axioms of the framework do not refer to the specific mathematical structure of quantum theory, and can therefore be exported in the context of any operational probabilistic theory.
The study of quantum information protocols that process quantum gates has led to an interest in ‘higher-order’ quantum transformations, which are transformations that act on other quantum transformations as inputs and/or return them as outputs. Mathematically, such transformations form an inductive hierarchy of infinitely many levels, or ‘orders’: quantum states are at order zero; channels, which transform quantum states, are at order one; superchannels, which transform channels, are at order two; maps that transform superchannels are at order three, and so on. To proceed toward a general understanding of higher-order quantum theory, we need methods to study the full inductive hierarchy in a uniform manner. In the context of the Hilbert space formalism of quantum theory, this means studying operator spaces (used to represent states), linear operators between operator spaces (used to represent channels), etc.; in other words, the inductive hierarchy of higher-order linear maps. We introduce a methodological framework for higher-order quantum theory, partly modeled on that of [Bisio \& Perinotti, 2019]. The framework is based on a set of types, denoted TypesA. Types may be thought of as labels that we use to identify and differentiate all the different kinds of objects of higher-order quantum theory. The central objects of the framework are typed (higher-order) linear maps, as given by the construction of a set L(x) of linear maps of type x for each x ∈ TypesA. We equip the framework with a parallel product operation for typed linear maps, which modifies and generalizes the tensor product so as to be physically meaningful when applied to maps of distinct and arbitrary orders. With the aim of characterizing the higher-order linear maps that represent valid quantum objects, we give a construction, consisting of a convex cone K(x) for each x ∈ TypesA, which generalizes the notion of complete positivity to all orders. We construct a version of the Choi isomorphism for our framework, and we use it to show that K(x) is self-dual for all x ∈ TypesA.
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.
Here we study the unitary groups that can be constructed using elements from the qubit Clifford Hierarchy. We first provide a necessary and sufficient canonical form that semi-Clifford and generalized semi-Clifford elements must satisfy to be in the Clifford Hierarchy. Then we classify the groups that can be formed from such elements. Up to Clifford conjugation, we classify all such groups that can be constructed using generalized semi-Clifford elements in the Clifford Hierarchy. We discuss a possible minor exception to this classification in the appendix. This may not be a full classification of all groups in the qubit Clifford Hierarchy as it is not currently known if all elements in the Clifford Hierarchy must be generalized semi-Clifford. In addition to the diagonal gate groups found by Cui et al., we show that many non-isomorphic (to the diagonal gate groups) generalized symmetric groups are also contained in the Clifford Hierarchy. Finally, as an application of this classification, we examine restrictions on transversal gates given by the structure of the groups enumerated herein which may be of independent interest.
We consider the problem of testing whether an unknown unitary is close to a specified level of the Clifford hierarchy. Bu, Gu, and Jaffe proposed a candidate tester for this task based on a connection with noncommutative analogues of the Gowers uniformity norms. The complexity of this tester -- whose analysis depends on a robust characterization of the near-extremizers of these norms -- was left open. We establish such a characterization for the fourth noncommutative uniformity norm and, as a consequence, obtain an efficient tester for the third level of the Clifford hierarchy. We further discuss possible routes toward resolving the problem of testing for all higher levels, highlighting the main barriers that remain.