Learning and Testing Algorithms for the Clifford Group

Abstract

Given oracle access to an unknown unitary C from the Clifford group and its conjugate, we give an exact algorithm for identifying C with O(n) queries, which we prove is optimal. We then extend this to all levels of the Gottesman-Chuang hierarchy (also known as the C_k hierarchy). Further, for unitaries not in the hierarchy itself but known to be close to an element of the hierarchy, we give a method of finding this close element. We also present a Clifford testing algorithm that decides whether a given black-box unitary is close to a Clifford or far from every Clifford.

7 pages

References in corpus (8)

• Quantum Teleportation is a Universal Computational Primitive
• Scalable multi-particle entanglement of trapped ions
• A Theory of Fault-Tolerant Quantum Computation
• Prescription for experimental determination of the dynamics of a quantum black box
• Quantum Error Correction and Orthogonal Geometry
• Complete Characterization of a Quantum Process: the Two-Bit Quantum Gate
• Tomography of Quantum Operations
• Choi's Proof and Quantum Process Tomography

Cited by in corpus (25)

• Qudits and high-dimensional quantum computing
• Direct Fidelity Estimation from Few Pauli Measurements
• Practical characterization of quantum devices without tomography
• Scalable measures of magic resource for quantum computers
• Qudit versions of the qubit "pi-over-eight" gate
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• A Survey of Quantum Property Testing
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Learning quantum circuits of some $T$ gates
• Property testing of unitary operators
• Unscrambling Quantum Information with Clifford decoders
• Learning quantum states and unitaries of bounded gate complexity
• Constructions for Quantum Indistinguishability Obfuscation
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Pseudo-randomness and Learning in Quantum Computation
• Learning stabilizer states by Bell sampling
• Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit
• Learning Quantum Processes with Quantum Statistical Queries
• Learning unitaries with quantum statistical queries
• Agnostic Process Tomography
• Clifford Circuits can be Properly PAC Learned if and only if $\text{RP}=\text{NP}$
• Adaptively secure unitary designs with constant non-Clifford cost
• Quantum certification of state set and unitary channel
• Process Tomography for Clifford Unitaries