A QCA for every SPT

Basic Information

• Paper ID: 2407.07951
• Title: A QCA for every SPT
• Authors: Lukasz Fidkowski (University of Washington), Jeongwan Haah (Microsoft Quantum), Matthew B. Hastings (Microsoft Quantum)
• Classification: cond-mat.str-el quant-ph
• Publication Date: arXiv:2407.07951v2 cond-mat.str-el 22 Nov 2024
• Paper Link: https://arxiv.org/abs/2407.07951

Abstract

In three dimensions, there exists a non-trivial quantum cellular automaton (QCA) that can disentangle the three-fermion Walker-Wang model, whose action depends on the Stiefel-Whitney classes of the spacetime manifold. This paper proposes a conjecture generalizing this to higher dimensions. For any time-reversal symmetric protected topological phase (SPT) depending on Stiefel-Whitney classes, we construct the corresponding QCA and conjecture that it can disentangle the phase. Some of our QCAs are Clifford, and we relate them to classification theorems for Clifford QCAs. We identify Clifford QCAs in $4m+1$ dimensions, finding that they can be described as low-depth circuits using non-Clifford gates but cannot be described using Clifford gates alone.

Research Background and Motivation

Problem Background

1. QCA Classification Problem: Quantum cellular automata (QCAs) are algebra automorphisms on lattice spin systems that preserve locality. While QCA classification in one dimension has been completely solved, the situation in higher dimensions is more complex and interesting.
2. Connection between SPT Phases and QCAs: Symmetry-protected topological (SPT) phases are important concepts in condensed matter physics. It is known that in three dimensions, there exists a non-trivial QCA that can disentangle the three-fermion Walker-Wang model, which corresponds to a time-reversal SPT phase beyond group cohomology classification.
3. Cobordism Classification: The complete classification of time-reversal SPT phases is given by cobordism theory, with its action described by products of Stiefel-Whitney classes.

Research Motivation

• Generalize the three-dimensional three-fermion QCA to arbitrary dimensions
• Establish a general correspondence between SPT phases and QCAs
• Understand the classification and properties of Clifford QCAs
• Explore the complexity differences of QCAs under different gate sets

Core Contributions

1. Propose SW-QCA Correspondence: Conjecture that any time-reversal SPT phase depending on products of Stiefel-Whitney classes can be generated by a corresponding QCA.
2. Construct High-Dimensional Walker-Wang Models: Generalize the three-dimensional {1,f} Walker-Wang model to arbitrary dimensions, describing $(n-1)$-dimensional "fermion" objects coupled to $n$-form Z₂ gauge fields.
3. Explicit Construction of Clifford QCAs: Construct Clifford QCAs in $2k+1$ dimensions and provide compact representations using polynomial formalism.
4. Prove Triviality in Even Cases: Rigorously prove that for even $k$, QCAs in $2k+1$ dimensions are trivial (can be written as circuits).
5. Clifford-hard but Non-Clifford-easy Phenomenon: Discover that certain QCAs require deep circuits with Clifford gates but only shallow circuits with non-Clifford gates.

Detailed Methods

Task Definition

Construct QCAs corresponding to arbitrary time-reversal SPT phases such that the QCA acting on product states can generate reversible phases with the given Stiefel-Whitney class action.

Core Construction Methods

1. High-Dimensional Bosonization Duality

Based on techniques from references 14-16, for arbitrary $n < d$ and sequences $\{i_s\}$ satisfying specific conditions, rewrite the $d$-dimensional bosonic spin Hilbert space as the Hilbert space of $n$-form Z₂ gauge fields coupled to $(n-1)$-dimensional extended objects.

2. Generalization of Walker-Wang Models

Construct generalized Walker-Wang Hamiltonian: $H^{WW}_{n,d} = -\sum_{\square^{d-n+1}} W_{\square^{d-n+1}} - \sum_{\square^{d-n-1}} (-1)^{\int (\square^{d-n-1} \cup^{d-2n-1} d\square^{d-n-1} + \square^{d-n-1} \cup^{d-2n-2} \square^{d-n-1})} B_{\square^{d-n-1}}$

where $W$ terms ensure electric field surfaces are closed, and $B$ terms are vertex terms.

3. QCA Definition

For $m$ different lattices, each corresponding to an $n_j$-form gauge field $a_j$, define the QCA: $U^{a_1 da_2...da_m}_i \equiv (-1)^{\int a_1 \cup da_2 \cup ... \cup da_m}$

where $i$ encodes information from sequences $\{i^j_s\}$.

Technical Innovations

1. Use of High-Dimensional Cup Products: Utilize high-dimensional cup products on hypercubic lattices to define fermionic signs and QCA actions.
2. Polynomial Formalism: For Clifford QCAs, use polynomial formalism to provide compact $4R \times 4R$ matrix representations, where $R = \binom{2k+1}{k}$.
3. Dimension Reduction Maps: Implement dimension reduction algorithms for Clifford QCA classification to compute Z₂ invariants.

Experimental Setup

Theoretical Verification Methods

1. Polynomial Formalism Verification: For $k=1,2$ (i.e., $d=3,5$), numerically verify that QCA matrices satisfy $M^\dagger \lambda M = \lambda$.
2. Reduction Map Computation: Implement symbolic computation of dimension reduction maps, computing non-zero Z₂ invariants for the $d=3$ case.
3. Field Theory Arguments: Provide field theory support for the SW-QCA correspondence through partition function calculations.

Specific Example Verification

• Three-fermion Case: Verify recovery of known three-fermion QCA for $k=1$
• Cluster State: Prove that the 0-form case produces cluster states
• Triviality Proof: Rigorously prove triviality of QCAs for even $k$

Experimental Results

Main Results

1. Clifford QCA Classification:
   • Non-trivial Clifford QCAs exist in odd spatial dimensions $d \geq 3$
   • Classification group is Z₂, consistent with predictions from reference 19
2. Triviality Results:
   • For even $k$, QCAs in $2k+1$ dimensions are trivial
   • Can be written as shallow circuits using non-Clifford gates
3. Complexity Separation:
   • For $m \geq 1$: $\lim_{L \to \infty} \text{depth}(U^{WW}_{4m+1}(L)) < \infty$$\lim_{L \to \infty} \text{depth}(U^{WW}_{4m+1}(L); \text{Clifford}) = \infty$

Specific Computational Results

1. Three-Dimensional Case: Through dimension reduction map computation, confirm that the $d=3$ Clifford QCA has non-zero Z₂ invariant.
2. Five-Dimensional Case: Although computationally complex, the first step of the reduction map was completed.
3. Matrix Representations: Provide explicit $4R \times 4R$ matrix representations for Clifford QCAs in $2k+1$ dimensions.

Related Work

QCA Classification Theory

• Gross et al. 2: Complete classification of one-dimensional QCAs
• Freedman and Hastings 9: Prove that two-dimensional QCAs are trivial under blending equivalence
• Haah 10,19: Classification theorems for Clifford QCAs

SPT Phase Theory

• Kapustin 11: Cobordism classification of time-reversal SPT phases
• Chen and Kapustin 14: Three-dimensional bosonization duality
• Fidkowski et al. 1,7: Three-fermion QCA and SPT phases beyond group cohomology

Walker-Wang Models

• Kitaev 12: Honeycomb model and fermionization
• Chen and Tata 15: High-dimensional cup products on hypercubic lattices

Conclusions and Discussion

Main Conclusions

1. SW-QCA Correspondence: Propose a general correspondence between SPT phases and QCAs, where any product of Stiefel-Whitney classes corresponds to a QCA.
2. Clifford Complexity: Discover complexity differences between Clifford gates and general quantum gates in implementing certain unitary operators.
3. High-Dimensional Generalization: Successfully generalize the three-dimensional three-fermion QCA to arbitrary odd dimensions.

Limitations

1. Conjectural Nature: The SW-QCA correspondence remains a conjecture lacking rigorous proof.
2. Incompleteness of Field Theory Arguments: Standard difficulties exist in computing partition functions on spacetime manifolds from lattice wavefunctions.
3. Computational Complexity: The dimension reduction map computation has at least doubly exponential complexity.

Future Directions

1. Rigorous Proof of SW-QCA Correspondence
2. Generalization to Branched Triangulations
3. Understanding Surface Theories of High-Dimensional QCAs
4. Characterizing General Criteria for QCA Non-Triviality

In-Depth Evaluation

Strengths

1. Theoretical Depth: Connect QCA theory with SPT phase classification, providing profound theoretical insights.
2. Constructive Approach: Not only propose conjectures but also provide concrete construction methods and computational techniques.
3. Multiple Verifications: Support main results through field theory arguments, lattice calculations, and specific examples.
4. Technical Innovation: Introduce high-dimensional cup products and polynomial formalism, providing new tools for QCA research.

Weaknesses

1. Insufficient Rigor: Many key results remain conjectures lacking completely rigorous proofs.
2. Computational Limitations: Due to computational complexity, unable to verify all predictions for high-dimensional cases.
3. Physical Interpretation: Lack rigorous lattice definitions for statistical properties of high-dimensional "fermion" objects.

Impact

1. Theoretical Contribution: Provide new framework for understanding relationships between QCAs and topological phases.
2. Computational Complexity Theory: The discovered Clifford-hard phenomenon has important implications for quantum computation theory.
3. Methodological Value: Developed technical methods applicable to other related problems.

Application Scenarios

1. Topological Quantum Computing: Provide theoretical foundation for designing quantum computing schemes based on SPT phases.
2. Condensed Matter Theory: Provide new theoretical tools for studying high-dimensional topological phases.
3. Quantum Information: Offer new perspectives for understanding topological properties of quantum entanglement.

References

The paper cites 42 important references, primarily including:

1. Haah, Fidkowski, Hastings (2023): High-dimensional non-trivial QCAs
2. Gross et al. (2012): One-dimensional QCA classification
3. Kapustin (2014): Cobordism classification of SPT phases
4. Chen, Kapustin (2019): Three-dimensional bosonization
5. Chen, Tata (2023): High-dimensional cup product theory