PaperlayerView exact revision on arXiv

Source-linked AI summary

Hadamard-free circuits expose the structure of the Clifford group

Sergey Bravyi, Dmitri Maslov

arXiv:2003.09412v2quant-phcs.ET

TL;DR

Clifford operators are central to several quantum protocols, motivating efficient ways to represent and generate them. This paper gives a unique, exactly minimal canonical form and uses it to obtain faster uniform sampling and circuit reductions, including a 9n-depth Linear Nearest Neighbor implementation.

  • Problem

    Clifford circuits support error correction, randomized benchmarking, and tomography, while their implementation overhead can dominate costs, motivating efficient representations and optimization.

    Source: §1 · p. 1

  • Method

    The authors construct a unique F1HSF2 decomposition using Hadamard-free circuit subgroups and develop a polynomial-time algorithm to compute it.

    Source: §1 · p. 2

  • Results

    The canonical form has exactly minimal degrees of freedom; its sampler runs in O(n^2), matching the information-theoretic lower bound in random bits.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The decomposition supports reduced measurement circuits and arbitrary Clifford implementation at two-qubit depth 9n on LNN; Hadamards can also lower entangling-gate counts.

    Source: §1 · p. 3

    Clifford-gate advantage over reversible CNOT circuits cannot exceed a constant factor.

    Source: §5 · p. 21

Abstract

from arXiv · show

The Clifford group plays a central role in quantum randomized benchmarking, quantum tomography, and error correction protocols. Here we study the structural properties of this group. We show that any Clifford operator can be uniquely written in the canonical form $F_1HSF_2$, where $H$ is a layer of Hadamard gates, $S$ is a permutation of qubits, and $F_i$ are parameterized Hadamard-free circuits chosen from suitable subgroups of the Clifford group. Our canonical form provides a one-to-one correspondence between Clifford operators and layered quantum circuits. We report a polynomial-time algorithm for computing the canonical form. We employ this canonical form to generate a random uniformly distributed $n$-qubit Clifford operator in runtime $O(n^2)$. The number of random bits consumed by the algorithm matches the information-theoretic lower bound. A surprising connection is highlighted between random uniform Clifford operators and the Mallows distribution on the symmetric group. The variants of the canonical form, one with a short Hadamard-free part and one allowing a circuit depth $9n$ implementation of arbitrary Clifford unitaries in the Linear Nearest Neighbor architecture are also discussed. Finally, we study computational quantum advantage where a classical reversible linear circuit can be implemented more efficiently using Clifford gates, and show an explicit example where such an advantage takes place.

1 Introduction

The introduction presents a uniquely parameterized, exactly minimal canonical decomposition of Clifford operators and uses it to motivate faster uniform sampling and circuit reductions. It also outlines measurement-oriented and Linear Nearest Neighbor decompositions and an example where Hadamards reduce entangling-gate cost for linear reversible functions.

1 Introduction

  • Clifford circuits support error correction and randomized benchmarking, while their overhead can dominate implementation cost, motivating circuit optimization.Uniform Clifford operators also support tomography and other protocols; the introduction notes their unitary 3-design property.Source: §1 · p. 1
  • Every Clifford operator has a unique F1HSF2 form with exactly minimal degrees of freedom and polynomial-time computable Hadamard-free factors.It fine-tunes the earlier seven-stage decomposition by moving as many gates from SF2 into F1 as possible.Source: §1 · p. 2
  • O(n^2) runtime generates a uniformly distributed n-qubit Clifford operator, versus O(n^3) for the prior algorithm, using the information-theoretic minimum number of random bits.The paper also highlights a connection to the Mallows distribution on the symmetric group.Source: §1 · p. 2
  • Before computational-basis measurement, one Hadamard-free stage can be skipped because its action can be replaced by classical postprocessing of measurement outcomes.This reduction is motivated by protocols such as shadow tomography and the final stage of randomized benchmarking.Source: §1 · p. 2
  • The reduced decomposition implements arbitrary Clifford circuits on a Linear Nearest Neighbor architecture with two-qubit gate depth 9n.The introduction also describes a decomposition for measurement settings that can use 2 two-qubit gates, where k is the canonical form’s number of Hadamards.Source: §1 · pp. 2–3
  • For entangling-gate count, certain linear reversible functions can be implemented more efficiently with Clifford circuits than with CNOT-only circuits.The paper frames this as a toy example of computational quantum advantage and develops resource-count bounds.Source: §1 · p. 3

2 Canonical form of Clifford circuits

This section develops a unique layered canonical form for Clifford operators, using Borel-group factors, a Hadamard layer, and a qubit permutation, and characterizes its subgroup constraints. It derives the form through disentangling and structured factorization, with polynomial-time and recursive procedures for computing its components.

2 Canonical form of Clifford circuits

  • Every n-qubit Clifford operator has a unique canonical form with Borel-group factors surrounding a Hadamard layer and qubit permutation.The two Borel factors are parameterized by matrices subject to conditions C1–C5.Source: §2 · p. 4
  • Conditions C1–C5 specify which entries of Γ and ∆ must vanish based on the Hadamard bits and permutation order.Source: §2 · p. 4
  • The canonical form can be computed in poly(n) time from the Clifford operator’s stabilizer tableaux.Source: §2 · p. 4
  • For fixed Hadamard layer and permutation, uniform sampling of the constrained matrices supports uniform Clifford generation, with the layer and permutation drawn from a generalized Mallows distribution.Source: §2 · p. 5

2.1 The existence and the uniqueness of the canonical form

  • Bruhat decomposition fixes the Hadamard-permutation layer, while a unique Borel-factor decomposition with a trivial Pauli part yields the unique canonical factors.Source: §2.1 · pp. 5–6
  • The matrix rules C1–C5 are necessary and sufficient for a Borel operator to belong to the relevant subgroup defined by the Hadamard layer and permutation.Source: §2.1 · pp. 6, 9

2.2 How to compute the canonical form

  • A non-entangling Clifford operator decomposes into single-qubit h-free factors, a Hadamard layer, and a permutation, and this decomposition is computable in O(n^2) time.Non-entangling means each transformed single-qubit X and Z operator remains a single-qubit Pauli operator.Source: §2.2 · pp. 9–10
  • The algorithm disentangles one qubit per step, recursively producing Hadamard-free operators that make B1UB2 non-entangling in time O(n3).The induction applies a single-qubit disentangling step to the remaining qubits until all n qubits are handled.Source: §2.2 · pp. 10, 12
  • Any Pauli operator can be conjugated to a single-qubit Pauli by some B ∈ Bn, with both operators computed in time O(n).The construction uses cnot↓ and cz gates.Source: §2.2 · pp. 10–11
  • A single-qubit disentangling step finds k, B1, and B2 such that B1UB2 is (1, k)-non-entangling in time O(n2).The operators used in the step are built from cz and downward cnot gates.Source: §2.2 · p. 11
  • Multiplying h-free circuits transforms one phase matrix to ∆1^TΓ2∆1 and combines phase stages by bitwise EXOR, since P and CZ are self-inverse.The multiplication rules express the product again as an h-free circuit of the parameterized form F(O, Γ, ∆).Source: §2.2 · p. 12
  • Finding K and M reduces to a uniquely solvable linear system with O(n2) variables and equations, solvable by standard algorithms in time O(n6).The system combines multiplication rules with linear constraints on the matrix parameters.Source: §2.2 · p. 13
  • The resulting decomposition is U = KWK′, with K ∈ Bn(¯h, S) and K′ ∈ Bn; K′’s Pauli part is fixed by comparing conjugated actions.This is the canonical form stated in Theorem 1.Source: §2.2 · p. 13

3 Generation of random Clifford operators

The canonical form enables exact uniform Clifford sampling in O(n^2) time using the information-theoretic minimum number of random bits. Its sampling procedure connects Clifford operators to a quantum analogue of the Mallows distribution and also yields a separate uniform sampler for GL(n).

3 Generation of random Clifford operators

  • The canonical-form algorithm samples a uniform n-qubit Clifford operator in O(n^2) time using log2 |Cn| random bits.It outputs the operator in canonical form; conversion to stabilizer tableaux takes O(n^ω) time.Source: §3 · pp. 13, 15
  • The simplified sampler for invertible binary matrices GL(n) runs in O(n^ω) time and uses exactly log2 |GL(n)| random bits.This improves on Randall’s sampler, which uses log2 |GL(n)| + O(1) bits.Source: §3 · p. 13
  • The quantum Mallows distribution links Hadamard-layer and permutation choices to the fraction of Clifford operators with those canonical-form components.It is described as a symplectic analogue of the Mallows distribution on permutations, with probabilities related to inversion counts.Source: §3 · p. 14
  • Algorithm 1 samples the quantum Mallows pair (h, S) in ˜O(n) time, using ˜O(1) time per iteration.The per-iteration sampling uses the geometric-series form of its probability vector.Source: §3 · pp. 14–15
  • Skipping Steps 14–31 still produces a uniform Clifford operator, but the simplified version is not optimal in random-bit use.The full algorithm’s random-bit consumption matches the information-theoretic lower bound.Source: §3 · pp. 13, 15

4 Clifford circuit reduction

The section modifies the canonical form to reduce gate counts and support short implementations for measurement-related tasks. Its reductions include a three-two-qubit-stage decomposition that gives arbitrary Clifford circuits a 9n two-qubit-gate-depth implementation on Linear Nearest Neighbor hardware.

4 Clifford circuit reduction

  • For a Clifford circuit followed by computational-basis measurement, a shorter circuit D can remove the introduced superposition and entanglement before measurement.The paper identifies randomized benchmarking as one setting where D is beneficial when shorter than C−1.Source: §4 · p. 17
  • For a Clifford operator with k Hadamards, a circuit D with at most nk−k(k+1)/2 two-qubit gates can make CD Hadamard-free.The gate count is that of the reduced f1 stage.Source: §4 · p. 17
  • Reducing the canonical form’s f1 stage leaves at most k(n−k) CNOT gates, k(k−1) CZ gates, and k phase gates.The reduction moves commuting CZ and phase gates into f2 and bounds the CNOT mapping by k(n−k).Source: §4 · p. 18
  • The Lemma 8 decomposition uses three two-qubit gate stages and implements arbitrary Clifford circuits at depth 9n on Linear Nearest Neighbor architecture.The paper gives this as an improvement over the previously known upper bound of 14n−4.Source: §4 · p. 18

5 Quantum advantage for CNOT circuits

Hadamard gates can reduce entangling-gate counts for some linear reversible functions, and the paper gives algorithms for finding such savings. It also bounds the advantage and conjectures how it compares with allowing qubit permutations.

5 Quantum advantage for CNOT circuits

  • Hadamard gates can reduce entangling-gate counts for some linear reversible functions compared with CNOT-only circuits.The entangling-gate count considers only CNOT and CZ gates.Source: §5 · p. 19
  • Testing whether H(b)WH(a) is h-free can identify a lower-gate implementation of W, with stated conditions under which the transformed circuit equals W.The sufficient conditions include U·L(a)=L(b) and Ux=(U−1)^T x for x∈L(a).Source: §5 · pp. 19–20
  • Two algorithms optimize two-qubit gates in CNOT circuits; one allows a subcircuit transformation that turns neighboring CNOTs into CZ gates induced by phase gates.The CZ gates can be induced without two-qubit gates when the relevant linear functions already occur in the circuit.Source: §5 · pp. 19–21
  • A Clifford implementation uses 7 two-qubit gates for an example whose CNOT-optimal implementation requires more, demonstrating an entangling-gate advantage.The example circuit is established as CNOT-optimal by breadth-first search.Source: §5 · p. 21
  • Clifford implementations improve CNOT counts by at most a constant factor, although the paper shows G<g in some cases.Here g is the minimum CNOT count using {cnot}, and G is the minimum using {p, h, cnot}.Source: §5 · pp. 21–22
  • The authors conjecture that Clifford-gate and relative-phase optimizations do not exceed the gains available by allowing qubit permutations.The conjecture compares optimal circuits under the stated gate libraries and cost metric.Source: §5 · p. 23

6 Conclusion

The paper develops an exactly optimal layered parametrization of the Clifford group and uses it for efficient sampling and circuit constructions. It also reports a 9n two-qubit-depth LNN implementation and an example of reduced entangling-gate count.

6 Conclusion

  • The paper develops an exactly optimal parametrization of the Clifford group by layered quantum circuits.The parametrization supports an O(n^2) algorithm for uniformly sampling n-qubit Clifford unitaries.Source: §6 · p. 23
  • The paper constructs a small circuit that removes entanglement from Clifford circuits and implements arbitrary Clifford circuits in LNN architecture at two-qubit depth 9n.Source: §6 · p. 23
  • The smallest linear reversible circuit with a Clifford-gate advantage needs 8 CNOT gates as a CNOT circuit but only 7 entangling gates as a Clifford circuit.Source: §6 · p. 23

A Generation of a random uniformly distributed Boolean invertible matrix

The section constructs a uniform sampler for invertible binary matrices using a unique LSR decomposition. Its permutation component follows the Mallows distribution, and the algorithm achieves exact random-bit optimality.

A Generation of a random uniformly distributed Boolean invertible matrix

B Proof of the existence of exact parametrization of the Clifford group

The appendix gives a shorter proof of an exact parametrization of Clifford operators. It establishes uniqueness by identifying the Hadamard layer and a coset representative before fixing the remaining factor.

B Proof of the existence of exact parametrization of the Clifford group

C Python implementation of Algorithm 1

The section provides Python code for Algorithm 1, including a function named `qmallows` that constructs a Hadamard layer and permutation layer. The implementation is also included in Qiskit.

C Python implementation of Algorithm 1

D Python implementation of Algorithm 2

The section provides Python code for Algorithm 2 in a function named `random_clifford`. The code builds component matrices and combines them into a full stabilizer tableau.

D Python implementation of Algorithm 2

  • The `random_clifford` function constructs F1 and F2 from Gamma and Delta matrices, then assembles the full stabilizer tableau.The implementation forms products and inverses for the component matrices before constructing F1 and F2.Source: D Python implementation of Algorithm 2 · pp. 33–34
  • The code fills Gamma2 and Delta2 with random bits, including symmetric off-diagonal entries in Gamma2.It also samples diagonal entries of Gamma2.Source: D Python implementation of Algorithm 2 · p. 34
  • Conditional on h and the ordering in S, the code samples entries for Gamma1 and Delta1.Separate conditions govern Gamma1 entries for pairs with different or matching h values, and Delta1 entries for several h and S cases.Source: D Python implementation of Algorithm 2 · p. 34
  • To assemble U, the implementation applies the permutation S to F2, swaps tableau rows for Hadamard-layer positions, and multiplies by F1.The returned tableau is the product F1 U modulo 2.Source: D Python implementation of Algorithm 2 · p. 35
Loading 2003.09412v2…