Approximate Unitary 3-Designs from Transvection Markov Chains

2020/10/30 by Xinyu Tan, Tan, Xinyu, Narayanan Rengaswamy +3
Computer Science · Mathematics · Physics and Astronomy · #Cellular Automata and Applications #Combinatorics #Discrete mathematics #FOS: Physical sciences #Markov chain #Mathematics #Pauli exclusion principle #Pauli matrices #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum mechanics #Quantum-Dot Cellular Automata #Qubit #Unitary group #Unitary matrix #Unitary state #quant-ph

paper · pdf · doi:10.48550/arxiv.2011.00128

published in arXiv (Cornell University) (Cornell University) · 25 pages, submitted to Designs, Codes and Cryptography

openalex publication_date 2020/10/30 · arxiv created 2021/05/25 · arxiv updated 2021/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Unitary k-designs are probabilistic ensembles of unitary matrices whose first k statistical moments match that of the full unitary group endowed with the Haar measure. In prior work, we showed that the automorphism group of classical ℤ₄-linear Kerdock codes maps to a unitary 2-design, which established a new classical-quantum connection via graph states. In this paper, we construct a Markov process that mixes this Kerdock 2-design with symplectic transvections, and show that this process produces an ε-approximate unitary 3-design. We construct a graph whose vertices are Pauli matrices, and two vertices are connected by directed edges if and only if they commute. A unitary ensemble that is transitive on vertices, edges, and non-edges of this Pauli graph is an exact 3-design, and the stationary distribution of our process possesses this property. With respect to the symmetries of Kerdock codes, the Pauli graph has two types of edges; the Kerdock 2-design mixes edges of the same type, and the transvections mix the types. More precisely, on m qubits, the process samples O(log(N⁵/ε)) random transvections, where N = 2^m, followed by a random Kerdock 2-design element and a random Pauli matrix. Hence, the simplicity of the protocol might make it attractive for several applications. From a hardware perspective, 2-qubit transvections exactly map to the Mølmer-Sørensen gates that form the native 2-qubit operations for trapped-ion quantum computers. Thus, it might be possible to extend our work to construct an approximate 3-design that only involves such 2-qubit transvections.

Related

• Approximate 3-designs and partial decomposition of the Clifford group representation using transvections
• Local random quantum circuits are approximate polynomial-designs
• Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup
• Derandomizing Quantum Circuits with Measurement-Based Unitary Designs
• Unitary k-designs without Hamiltonian quenches