Complexity Classification of Conjugated Clifford Circuits

Adam Bouland, Joseph F. Fitzsimons, Dax Enshan KohCcc 2018 · DOI

TL;DR

This paper introduces "conjugated Clifford circuits" (CCCs) and fully classifies their computational power. They show that these circuits can perform hard sampling tasks, meaning they are computationally difficult to simulate classically, unless the polynomial hierarchy collapses. This work helps bridge the gap between efficiently simulable quantum circuits and fully universal quantum computers.

What Problem Does This Paper Address?

Quantum computers promise to solve problems intractable for classical computers, but building universal quantum computers is challenging. This has led to interest in "weak" quantum models that might offer a computational advantage with simpler hardware. Clifford circuits are a well-studied example of such a weak model; they are efficiently simulable classically. This paper investigates a modification of Clifford circuits called "conjugated Clifford circuits" (CCCs). The key question is: what is the computational power of these CCCs, and how does it depend on the specific conjugation operation used? This is important for understanding the landscape of quantum computational complexity and identifying potential pathways to quantum advantage.

Methods

The authors introduce "conjugated Clifford circuits" (CCCs) by taking standard Clifford circuits and conjugating each qubit's operation by a fixed one-qubit unitary $U$. Their primary method for classifying the hardness of simulating these CCCs involves:

  • Decomposition of $U$: They decompose the conjugating unitary $U$ into a product of rotations, $U = e^{i\alpha} R_z(\phi) R_x(\theta) R_z(\lambda)$, and analyze the complexity based on the parameters $\phi$ and $\theta$.
  • Postselection Gadgets: For hardness proofs, they employ postselection gadgets. These are circuit fragments that, when combined with postselection (discarding runs that don't meet certain criteria), can simulate universal quantum computation. This technique is adapted from previous work on quantum sampling problems.
  • Complexity Theory Tools: They leverage concepts from computational complexity theory, such as the polynomial hierarchy (PH), and the relationship between sampling problems and complexity classes like PP and BPP. They also use standard techniques like Markov's inequality and anticoncentration lemmas.
  • Classification of Unitaries: A significant part of their work involves classifying the conjugating unitary $U$ based on its rotational parameters to determine whether the resulting CCCs are efficiently simulable or computationally hard.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Conjugation Matters: The specific choice of the one-qubit unitary $U$ used for conjugation dramatically impacts the computational power of the resulting CCCs. Some choices of $U$ lead to efficiently simulable circuits, while others lead to computationally hard sampling problems.
  • Bridging the Gap: CCCs occupy an interesting intermediate space between efficiently simulable Clifford circuits and fully universal quantum computers. They are not universal by construction but can exhibit computational hardness.
  • Role of $Z$-rotations: The paper highlights that if $U$ is a Clifford operation times a $Z$-rotation, the resulting CCCs are efficiently simulable. This provides a clear boundary for when hardness emerges.
  • Postselection for Universality: Postselection, a non-physical but theoretically useful tool, is shown to be crucial for demonstrating the universality of CCCs for certain choices of $U$.
  • Additive vs. Multiplicative Error: The paper distinguishes between hardness for multiplicative error (exact simulation) and additive error (approximate simulation), showing hardness results for both, with additive error being more relevant for experimental settings.

Key Results

  • Complete Classification: The paper provides a complete classification of the computational power of CCCs based on the conjugating unitary $U$.
  • PH-Supremacy: For most choices of $U$ (specifically, those not a Clifford times a $Z$-rotation), CCCs are shown to be "PH-supreme." This means that if they could be efficiently simulated classically, it would imply a collapse of the polynomial hierarchy, a major event in computational complexity theory.
  • Hardness for Sampling: CCCs can perform sampling tasks that are believed to be hard for classical computers, requiring the polynomial hierarchy to collapse for efficient simulation (unless the error is very small).
  • Additive Error Hardness: Under additional complexity-theoretic conjectures, CCCs are shown to be hard to simulate even with constant additive error.

Limitations and Future Work

  • Conjecture Dependence: The hardness results for additive error rely on specific complexity-theoretic conjectures (Conjectures 4.1 and 4.2) about the difficulty of approximating output probabilities. While the worst-case version of Conjecture 4.2 is proven, the average-case version remains a conjecture.
  • Non-Relativizing Proofs: The authors note that proving Conjecture 4.2 would likely require non-relativizing techniques, meaning the proof might not hold if classical oracles were allowed in the quantum circuit.
  • Open Problems: The paper lists several open problems, including:
  • Classifying the computational complexity of commuting CCCs.
  • Extending hardness results to two-qubit Clifford gates conjugated by non-tensor-product unitaries.
  • Investigating quantum advantage with lower-depth CCC circuits.
  • Proving the average-case hardness conjecture for CCCs.
  • Determining if quantum advantage can be achieved with CCCs of lower depth.

Summary updated

BibTeX
@inproceedings{bouland2018complexity,
  author = {Adam Bouland and Joseph F. Fitzsimons and Dax Enshan Koh},
  title = {{Complexity Classification of Conjugated Clifford Circuits}},
  booktitle = {Ccc},
  year = {2018},
  doi = {10.4230/lipics.ccc.2018.21},
}
Figure