Quantum t-designs: t-wise independence in the quantum world

2007/01/17 by Andris Ambainis, Ambainis, Andris, Joseph Emerson +1 · 21 citations
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0701126

19 pages, v2 two references added, to appear in Complexity'06

openalex publication_date 2007/01/17 · arxiv created 2007/02/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states, w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t. We then show that an approximate 4-design provides a derandomization of the state-distinction problem considered by Sen (quant-ph/0512085), which is relevant to solving certain instances of the hidden subgroup problem.

Cited by

• Stable low-rank matrix recovery from 3-designs
• Approximate pushforward designs and image bounds on approximations
• Quantum ramp secret sharing from Haar scrambling
• Realizing Unitary k-designs with a Single Quench
• Apparent Universal Behavior in Second Moments of Random Quantum Circuits
• Quantum Relative Entropy Decay Composition Yields Shallow, Unstructured k-Designs
• Exponential Speed-ups for Structured Goemans-Williamson relaxations via Quantum Gibbs States and Pauli Sparsity
• On Limits on the Provable Consequences of Quantum Pseudorandomness
• Creating Qubit States with Degenerate Two-level Systems
• Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms
• Quantum State Tomography for Tensor Networks in Two Dimensions
• Approximating the operator norm of local Hamiltonians via few quantum states
• Duality of extremal quantum states in verification and data hiding
• Adaptive t Design Dummy-Gate Obfuscation for Cryogenic Scale Enforcement
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• Exact distinguishability between real-valued and complex-valued Haar random quantum states
• Learning Encodings by Maximizing State Distinguishability: Variational Quantum Error Correction
• Quantum Routing and Entanglement Dynamics Through Bottlenecks
• Entanglement dynamics and Page curves in random permutation circuits
• Learning to Concatenate Quantum Codes
• Hardness of observing strong-to-weak symmetry breaking
• Quantum One-Way Functions and Related Cryptographic Primitives

Related

• Efficient approximate unitary t-designs from partially invertible\n universal sets and their application to quantum speedup
• A quantum Johnson-Lindenstrauss lemma via unitary t-designs
• Approximate t-designs in generic circuit architectures
• Exact distinguishability between real-valued and complex-valued Haar random quantum states
• Derandomizing Quantum Circuits with Measurement-Based Unitary Designs