Complexity Classification of Conjugated Clifford Circuits

2017/09/06 by Adam Bouland, Joseph F. Fitzsimons, Dax Enshan Koh · 10 citations
Chemistry · Computer Science · Engineering · Physics and Astronomy · #Chemistry #Computer science #Conjugated system #Electrical engineering #Electronic circuit #Engineering #Organic chemistry #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum-Dot Cellular Automata #cs.CC #quant-ph

paper · pdf · open access · doi:10.4230/lipics.ccc.2018.21

published in DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) (Schloss Dagstuhl – Leibniz Center for Informatics) · 31 pages

openalex publication_date 2017/09/06 · arxiv created 2018/05/29 · arxiv updated 2018/06/21 · openalex created_date 2020/11/23 · openalex updated_date 2026/08/05

Abstract

Clifford circuits - i.e. circuits composed of only CNOT, Hadamard, and pi/4 phase gates - play a central role in the study of quantum computation. However, their computational power is limited: a well-known result of Gottesman and Knill states that Clifford circuits are efficiently classically simulable. We show that in contrast, "conjugated Clifford circuits" (CCCs) - where one additionally conjugates every qubit by the same one-qubit gate U - can perform hard sampling tasks. In particular, we fully classify the computational power of CCCs by showing that essentially any non-Clifford conjugating unitary U can give rise to sampling tasks which cannot be efficiently classically simulated to constant multiplicative error, unless the polynomial hierarchy collapses. Furthermore, by standard techniques, this hardness result can be extended to allow for the more realistic model of constant additive error, under a plausible complexity-theoretic conjecture. This work can be seen as progress towards classifying the computational power of all restricted quantum gate sets.

Citations

• Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations
• Scalable and Robust Randomized Benchmarking of Quantum Processes
• Quantum computing and the entanglement frontier
• Measurement-based quantum computation
• On the Structure of Polynomial Time Reducibility
• Measurement-based quantum computation with cluster states
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum computing, postselection, and probabilistic polynomial-time
• Universal Refocusing of Systematic Quantum Noise
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Characterizing quantum supremacy in near-term devices
• Hardness of classically sampling the one-clean-qubit model with constant total variation distance error
• On the Complexity of Random Quantum Computations and the Jones Polynomial