Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1709.01805 · Leibniz international proceedings in informatics

Complexity Classification of Conjugated Clifford Circuits

Adam Bouland, Joseph F. Fitzsimons, Dax Enshan Koh

Published Sep 6, 2017• 43 citations
arXivHTMLPDF

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.

DOI
10.4230/lipics.ccc.2018.21

Related papers

Classical simulation complexity of restricted models of quantum computation

Dax Enshan Koh

Restricted models of quantum computation are mathematical models which describe quantum computers that have limited access to certain resources. Well-known examples of such models include the boson sampling model, extended Clifford circuits, and instantaneous quantum polynomial-time circuits. While unlikely to be universal for quantum computation, several of these models appear to be able to outperform classical computers at certain computational tasks, such as sampling from certain probability distributions. Understanding which of these models are capable of performing such tasks and characterizing the classical simulation complexity of these models--i.e. how hard it is to simulate these models on a classical computer--are some of the central questions we address in this thesis. Our first contribution is a classification of various extended Clifford circuits according to their classical simulation complexity.

•Jan 1, 2019•0 citations

Quantum advantage of unitary Clifford circuits with magic state inputs

Mithuna Yoganathan, Richard Jozsa, Sergii Strelchuk

We study the computational power of unitary Clifford circuits with solely magic state inputs (CM circuits), supplemented by classical efficient computation. We show that CM circuits are hard to classically simulate up to multiplicative error (assuming polynomial hierarchy non-collapse), and also up to additive error under plausible average-case hardness conjectures. Unlike other such known classes, a broad variety of possible conjectures apply. Along the way, we give an extension of the Gottesman-Knill theorem that applies to universal computation, showing that for Clifford circuits with joint stabilizer and non-stabilizer inputs, the stabilizer part can be eliminated in favour of classical simulation, leaving a Clifford circuit on only the non-stabilizer part. Finally, we discuss implementational advantages of CM circuits.

arXiv:1806.03200•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•May 1, 2019•57 citations

(A Variant of) Clifford Circuit Synthesis is NP-Complete

Luna Lima Keller, Richard Kueng

Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.

quant-pharXiv:2610.02029•Oct 2, 2026•2 citations

The power of restricted quantum computational models

Mithuna Yoganathan

Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.

•Jan 5, 2021•1 citation

Classical simulation complexity of extended Clifford circuits

Richard Jozsa, M. Van den Nest

Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs. weak simulation, (b) inputs being computational basis states vs. general product states, (c) adaptive vs. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line outputs. We consider the classical simulation complexity of all combinations of these ingredients and show that many are not classically efficiently simulatable (subject to common complexity assumptions such as P not equal to NP). Our results reveal a surprising proximity of classical to quantum computing power viz. a class of classically simulatable quantum circuits which yields universal quantum computation if extended by a purely classical additional ingredient that does not extend the class of quantum processes occurring.

arXiv:1305.6190•Quantum Information and Computation•May 1, 2014•97 citations

Further extensions of Clifford circuits and their classical simulation complexities

Dax Enshan Koh

Extended Clifford circuits straddle the boundary between classical and quantum computational power. Whether such circuits are efficiently classically simulable seems to depend delicately on the ingredients of the circuits. While some combinations of ingredients lead to efficiently classically simulable circuits, other combinations, which might just be slightly different, lead to circuits which are likely not. We extend the results of Jozsa and Van den Nest [Quant. Info. Comput. 14, 633 (2014)] by studying two further extensions of Clifford circuits. First, we consider how the classical simulation complexity changes when we allow for more general measurements. Second, we investigate different notions of what it means to ‘classically simulate’ a quantum circuit. These further extensions give us 24 new combinations of ingredients compared to Jozsa and Van den Nest, and we give a complete classification of their classical simulation complexities. Our results provide more examples where seemingly modest changes to the ingredients of Clifford circuits lead to “large” changes in the classical simulation complexities of the circuits, and also include new examples of extended Clifford circuits that exhibit “quantum supremacy”, in the sense that it is not possible to efficiently classically sample from the output distributions of such circuits, unless the polynomial hierarchy collapses.

arXiv:1512.07892•Quantum Information and Computation•Mar 1, 2017•32 citations
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.
Restricted models of quantum computation are mathematical models which describe quantum computers that have limited access to certain resources. Well-known examples of such models include the boson sampling model, extended Clifford circuits, and instantaneous quantum polynomial-time circuits. While unlikely to be universal for quantum computation, several of these models appear to be able to outperform classical computers at certain computational tasks, such as sampling from certain probability distributions. Understanding which of these models are capable of performing such tasks and characterizing the classical simulation complexity of these models--i.e. how hard it is to simulate these models on a classical computer--are some of the central questions we address in this thesis. Our first contribution is a classification of various extended Clifford circuits according to their classical simulation complexity.
We study the computational power of unitary Clifford circuits with solely magic state inputs (CM circuits), supplemented by classical efficient computation. We show that CM circuits are hard to classically simulate up to multiplicative error (assuming polynomial hierarchy non-collapse), and also up to additive error under plausible average-case hardness conjectures. Unlike other such known classes, a broad variety of possible conjectures apply. Along the way, we give an extension of the Gottesman-Knill theorem that applies to universal computation, showing that for Clifford circuits with joint stabilizer and non-stabilizer inputs, the stabilizer part can be eliminated in favour of classical simulation, leaving a Clifford circuit on only the non-stabilizer part. Finally, we discuss implementational advantages of CM circuits.
Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.
Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.
Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs. weak simulation, (b) inputs being computational basis states vs. general product states, (c) adaptive vs. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line outputs. We consider the classical simulation complexity of all combinations of these ingredients and show that many are not classically efficiently simulatable (subject to common complexity assumptions such as P not equal to NP). Our results reveal a surprising proximity of classical to quantum computing power viz. a class of classically simulatable quantum circuits which yields universal quantum computation if extended by a purely classical additional ingredient that does not extend the class of quantum processes occurring.
Extended Clifford circuits straddle the boundary between classical and quantum computational power. Whether such circuits are efficiently classically simulable seems to depend delicately on the ingredients of the circuits. While some combinations of ingredients lead to efficiently classically simulable circuits, other combinations, which might just be slightly different, lead to circuits which are likely not. We extend the results of Jozsa and Van den Nest [Quant. Info. Comput. 14, 633 (2014)] by studying two further extensions of Clifford circuits. First, we consider how the classical simulation complexity changes when we allow for more general measurements. Second, we investigate different notions of what it means to ‘classically simulate’ a quantum circuit. These further extensions give us 24 new combinations of ingredients compared to Jozsa and Van den Nest, and we give a complete classification of their classical simulation complexities. Our results provide more examples where seemingly modest changes to the ingredients of Clifford circuits lead to “large” changes in the classical simulation complexities of the circuits, and also include new examples of extended Clifford circuits that exhibit “quantum supremacy”, in the sense that it is not possible to efficiently classically sample from the output distributions of such circuits, unless the polynomial hierarchy collapses.