PaperlayerView exact revision on arXiv

Source-linked AI summary

Trapdoored Clifford Operators and Applications

Minki Hhan, Hojune Lee

arXiv:2610.01848v1quant-phcs.CCcs.CR

TL;DR

Uniformly random Clifford operators are expensive to sample and implement, motivating a pseudorandom alternative with hidden efficient implementations. The paper constructs trapdoored Clifford and finite-field matrix distributions under variants of ring-LPN. Given the trapdoor, these operators admit near-linear resource bounds and fast Pauli-label action, with polylogarithmic-depth implementation under all-to-all connectivity.

  • Problem

    Sampling and implementing uniformly random n-qubit Cliffords incurs near-quadratic complexity, motivating a pseudorandom alternative that retains usefulness for polynomial-time quantum applications.

    Source: §1 · p. 3

  • Method

    Under variants of ring-LPN, the paper constructs trapdoored Clifford and finite-field matrix distributions whose hidden descriptions enable efficient implementation and matrix actions.

    Source: §1 · p. 3, §1.1 · p. 3

  • Results

    Trapdoored Cliffords can be sampled and implemented with n^(1+ε) time and resources, while supporting near-linear Pauli-label action and polylogarithmic-depth implementation under all-to-all connectivity.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The constructions provide a pseudorandom alternative to uniform Cliffords for many applications involving polynomial-time quantum computations.

    Source: §1 · p. 3

    The constructions rely on standard or strong (dual) ring-LPN assumptions; the stated noise-rate conjecture is proposed for ε(n) = (log n)^c/n with fixed c > 2.

    Source: §2.2 · p. 7

Abstract

from arXiv · show

Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However, sampling and implementing uniformly random $n$-qubit Clifford incur near-quadratic complexity due to the size of Clifford group. We introduce a cryptographic way to overcome these barriers: trapdoored Clifford operator distributions whose samples are computationally indistinguishable from uniformly random Cliffords, yet implementing them can be much faster given the trapdoor. We construct a distribution of trapdoored Clifford operators whose elements can be sampled and implemented in near-linear time under a variant of the learning parity with noise assumption. Our constructions allow fast tableau action on Pauli labels for classical simulation, and also can be optimized to admit polylogarithmic-depth implementation. Along the way, we construct trapdoored matrices over finite fields that support efficient multiplication by both a matrix and its inverse, resolving an open question left by Vaikuntanathan and Zamir [SODA'26]. We use these constructions to obtain faster protocols based on random Cliffords. We also explore their applications to the worst-case to average-case reductions for matrix and Clifford problems including the iterated matrix multiplication and Clifford circuit synthesis. In particular, we show the hardness of batching Clifford circuits: synthesizing circuits that apply the same Clifford to multiple registers is at least as hard as worst-case matrix multiplication, even when synthesis succeeds on a small constant fraction of random Cliffords. This extends to approximate implementations by general quantum circuits.

1 Introduction

Uniformly random Clifford operators are costly to sample and implement, so the paper asks whether pseudorandomness can retain their usefulness while enabling hidden, efficient implementations. It constructs trapdoored Clifford operators and matrices, then applies them to Clifford-based protocols and worst-case-to-average-case reductions.

1 Introduction

  • The trapdoored Clifford samples are computationally indistinguishable from uniform Cliffords, while their hidden efficient circuit descriptions serve as trapdoors.The paper argues this relaxation suffices for most applications involving polynomial-time quantum computations.Source: §1 · p. 3

1.1 Our Results

  • Under (dual) ring-LPN, trapdoored Cliffords can be sampled and implemented with n^(1+ε) resources, with quasi-linear time under subexponential hardness.The trapdoor gives an implementation using n^(1+ε) elementary gates and clean ancillas; Pauli-label action is near-linear, and implementation can have polylogarithmic depth under all-to-all connectivity.Source: §1.1 · p. 3
  • Trapdoored finite-field matrices support efficient multiplication and inversion under the same assumptions, resolving an open question from [VZ26, Section 3].The constructions include triangular and symmetric matrices and support efficient determinant computation, addressing another question in.Source: §1.1 · p. 3

1.2 Applications

  • The constructions can replace uniform random Cliffords in protocols, including faster Pauli calculations for stabilizer simulation and direct fidelity estimation.For Clifford authentication, the paper proves negligible soundness error against all adversarial behavior.Source: §1.2 · p. 4
  • For classical shadows, trapdoored Cliffords may lose the exact 3-design property but appear as an approximate 3-design to efficient algorithms.The proposed use applies Cliffords to an unknown state and records outcomes for later prediction of efficiently computable observables.Source: §1.2 · p. 4
  • The paper extends worst-case-to-average-case reductions to linear-algebra and Clifford problems, including iterated matrix multiplication and Clifford circuit synthesis.It also connects batching the same Clifford across registers to worst-case matrix multiplication.Source: Worst-case to average-case reductions · p. 4

Worst-case to average-case reductions.

The paper extends worst-case-to-average-case reductions for linear-algebra and Clifford problems. Its results include reductions for iterated matrix multiplication and determinant computation, plus a hardness connection between batched Clifford synthesis and matrix multiplication.

Worst-case to average-case reductions.

  • Trapdoored invertible matrices yield worst-case-to-average-case reductions for linear-algebra and Clifford problems, extending the framework of.The paper identifies iterated matrix multiplication and determinant computation as its main linear-algebra applications.Source: Worst-case to average-case reductions · p. 4
  • An algorithm that synthesizes C⊗n from a random 2n-qubit Clifford tableau with constant success probability yields an algorithm for multiplying any two n × n matrices over F2 with high probability.The connection persists for approximate implementations by general quantum circuits, even when synthesis succeeds on an arbitrarily small constant fraction of random Cliffords.Source: Worst-case to average-case reductions · p. 4
  • The iterated matrix multiplication reduction works even when the given algorithm is correct on only a tiny fraction of inputs.The determinant reduction works with error rate 1/2 + ε for sufficiently large q.Source: Worst-case to average-case reductions · p. 4

2 Trapdoored Matrix Distributions

This section develops trapdoored matrix distributions from (dual) ring-LPN and extends the constructions from triangular matrices to invertible triangular matrices and all of GL(n, Fq), with efficient multiplication and inverse actions. It also gives exact determinant evaluation and fast power actions for pseudorandom conjugates, and extends inverse evaluation to polylogarithmic-depth circuits.

2.1 Definition

  • A trapdoored matrix distribution samples a matrix whose marginal is computationally indistinguishable from uniform and supplies correct trapdoor circuits for supported mappings.The trapdoor circuits compute the specified matrix-dependent mappings on every input.Source: §2.1 · p. 5

2.2 Base Construction from (Dual) Ring-LPN Assumptions

  • For m=Θ(n) and ε(n)=(log n)^c/n with c>2, under Conjecture 2.4 the base construction is O(nmε)-samplable and supports O(nmε)-efficient multiplication.Its sampling and circuit evaluation run in O(nmε+n log^2 n) time with overwhelming probability; the sparse-error cost dominates for these parameters.Source: §2.2 · p. 8

2.3 Trapdoored Triangular Matrices

  • Triangular-matrix distributions support multiplication with O(n^{1+δ}) sampling and evaluation under standard ring-LPN, or O(n) under strong ring-LPN.The standard bound holds for any fixed 0<δ<1; the strong-assumption construction uses a base dimension b=⌈8 log^c n⌉ with cα>1.Source: §2.3 · p. 9
  • The triangular-matrix sampling algorithm runs in O(n log^{c+1} n+nb) time with overwhelming probability, and its multiplication circuit has size O(n log^{c+1} n+nb).The parameter b is the chosen base dimension.Source: §2.3 · pp. 10–11
  • For U◦_n, U_n, L_n, and Sym_n, standard (dual) ring-LPN yields Õ(n^{1+δ}) sampling and mult/multT evaluation, and the strong assumption yields Õ(n) bounds.The distributions are computationally indistinguishable from uniform over their respective matrix families.Source: §2.3 · p. 11

2.4 Trapdoored Invertible Triangular Matrices with Efficient Inversion

  • For invertible upper-triangular matrices, standard (dual) ring-LPN gives Õ(n^{1+δ}) sampling and evaluation, while strong (dual) ring-LPN gives Õ(n) bounds for all four actions.Transposition extends the same guarantees to invertible lower-triangular matrices, interchanging multiplication with transpose multiplication and inversion with inverse-transpose.Source: §2.4 · pp. 12, 14

2.5 Trapdoored Invertible Matrices with Efficient Inversion

  • Under the standard (dual) ring-LPN assumption, trapdoored GL(n, Fq) samples support mult, multT, inv, and invT in Õ(n^{1+δ}) time; under the strong assumption, these bounds are Õ(n).The construction is computationally indistinguishable from a uniform GL(n, Fq) element and combines two trapdoored triangular factors with a permutation sampled from the Mallows distribution.Source: §2.5 · pp. 14–15
  • Given the trapdoor for a matrix sampled from the GL(n, Fq) construction, its determinant can be computed exactly in O(n) time.Writing the matrix as UσV lets the sampler use the diagonal entries of U and V and the cycle structure of σ.Source: §2.5 · p. 15
  • Under strong (dual) ring-LPN, for block-diagonal B with polylogarithmic-size blocks, A = GBG^-1 is indistinguishable from uniform in B's conjugacy class and supports Õ(n)-time Akv evaluation.This holds for every vector v and integer 1 ≤ k ≤ n^O(1), including computation of the block powers.Source: §2.5 · p. 15
  • Under standard dual ring-LPN, the evaluation guarantee holds in eO(n^(1+δ)) time for any fixed 0 < δ < 1, and similarity transforms transfer linear circuits with only basis-change costs added.Pseudorandomness is relative to Cl(B), since conjugation preserves the characteristic polynomial and other similarity invariants of B.Source: §2.5 · p. 16

2.6 Depth-Efficient Implementation

  • Theorem 2.23 gives modified samplers whose mult, multT, inv, and invT circuits have depth O(log^2 n), with unchanged sampling and circuit-size bounds.The resulting matrix distribution is computationally indistinguishable from uniform random matrices.Source: §2.6 · p. 16
  • Factored block descriptions use balanced sums and fast polynomial multiplication, while parallel diagonal-block actions and a logarithmic-depth shear yield overall depth O(log^2 n).At dimensions d ≤ b, uniform off-diagonal blocks are used; the hardness assumption is needed only above that cutoff.Source: §2.6 · p. 16

3 Trapdoored Clifford Distributions

The construction replaces the uniform Borel factors in the Bravyi–Maslov sampler with trapdoored factors while retaining a uniform Clifford distribution up to computational indistinguishability. Under ring-LPN assumptions, the trapdoors support efficient quantum application and classical tableau action, with near-linear resource bounds and an optional polylogarithmic-depth implementation.

3.1 Uniform random Clifford Oprators and Decomposition of Clifford Operators

  • The Bravyi–Maslov decomposition supplies the sampler framework: its quantum Mallows layer and uniform Pauli corrections are retained while uniform matrix factors are replaced.The original full factorization takes O(n²) time to sample and record.Source: §3.1 · pp. 17–18

3.2 Trapdoored Hadamard-free Clifford Operators

  • Hadamard-free Clifford distributions are pseudorandom and support efficient quantum application and tableau evaluation under standard or strong ring-LPN assumptions.The respective sampling and circuit-size bounds are eO(n^{1+δ}) and eO(n); correctness holds for every sample, while resource bounds hold with overwhelming probability.Source: §3.2 · p. 19
  • The construction also supports inverse quantum and tableau actions, and composition and inversion preserve efficient action circuits for the resulting operators.The inverse actions have the same asymptotic bounds, and composing forward and inverse circuits incurs O(T(n))-size circuits.Source: §3.2 · p. 20

3.3 Trapdoored Clifford Operators

  • Replacing the sampler’s two uniform Borel factors with independent trapdoored factors preserves pseudorandomness while retaining efficient quantum and tableau actions.The Hadamard and permutation layers add only linear overhead to sampling and evaluation.Source: §3.1 · p. 18, §3.3 · pp. 20–21
  • Under ring-LPN assumptions, full Clifford samples are computationally indistinguishable from uniform and support near-linear sampling, quantum application, and classical tableau evaluation.The standard assumption gives eO(n^{1+δ}) bounds for any fixed 0 < δ < 1; the strong variant gives eO(n) bounds.Source: §3.3 · p. 20
  • With all-to-all connectivity, the constructions can achieve O(log³ n) quantum-application depth while retaining the same gate-count and ancilla bounds.The depth-efficient variant also supports inverse application.Source: §3.3 · p. 21

4 Applications

The paper applies trapdoored Cliffords to authentication and worst-case-to-average-case reductions for matrix and Clifford problems. These applications include determinant and iterated matrix multiplication reductions, Clifford circuit synthesis, and reductions from parallel Clifford implementation to matrix multiplication, including approximate general-circuit implementations.

4.1 Clifford authentication

  • Trapdoored Clifford authentication has perfect completeness and ε + negl(n) soundness under the pseudorandomness assumption.Key generation, encoding, and decoding run in n^{1+o(1)} time with overwhelming probability under the strong ring-LPN assumption.Source: §4.1 · p. 22

4.2 Worst-case to Average-case Reductions

  • An average-case algorithm for iterated matrix multiplication yields a worst-case algorithm for products of d invertible matrices in eO(T(n)) time.The reduction assumes strong (dual) ring-LPN and a polynomially bounded d ≥ 2.Source: §4.2 · pp. 22–23
  • The determinant reduction computes determinants from an average-case algorithm over uniform matrices, with success thresholds depending on the field size.For q > 2, success probability at least 1/2 + ε on uniform GL(n, Fq) suffices.Source: §4.2 · p. 23
  • An average-case Clifford circuit synthesizer gives a worst-case implementation algorithm for any signed Clifford tableau in eO(T(n)) time.The output implementation uses clean ancillas with high probability.Source: §4.2 · p. 24

4.3 From average-case parallel Clifford implementations to matrix multiplication

  • Average-case parallel Clifford circuit implementation is at least as hard as worst-case matrix multiplication: a classical algorithm recovers AB in eO(T(n)) time.The synthesis input is a signed tableau of a 2n-qubit Clifford, and the output circuit acts on 2n² qubits.Source: §4.3 · p. 24
  • The matrix-multiplication reduction extends to approximate, possibly non-Clifford circuits, yielding a quantum algorithm for AB in eO(T(n)) time.The theorem assumes constant ε and η in [0, 1) and the quantum-secure strong ring-LPN assumption.Source: §4.3 · p. 25
Loading 2610.01848v1…