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:1508.02695 · npj Quantum Information

Hierarchy of universal entanglement in 2D measurement-based quantum computation

Jacob Miller, Akimasa Miyake

Published Nov 14, 2016• 91 citations
arXivHTMLPDF

Abstract

Abstract Measurement-based quantum computation (MQC) is a paradigm for studying quantum computation using many-body entanglement and single-qubit measurements. Although MQC has inspired wide-ranging discoveries throughout quantum information, our understanding of the general principles underlying MQC seems to be biased by its historical reliance upon the archetypal 2D cluster state. Here we utilise recent advances in the subject of symmetry-protected topological order (SPTO) to introduce a novel MQC resource state, whose physical and computational behaviour differs fundamentally from that of the cluster state. We show that, in sharp contrast to the cluster state, our state enables universal quantum computation using only measurements of single-qubit Pauli X , Y , and Z operators. This novel computational feature is related to the ‘genuine’ 2D SPTO possessed by our state, and which is absent in the cluster state. Our concrete connection between the latent computational complexity of many-body systems and macroscopic quantum orders may find applications in quantum many-body simulation for benchmarking classically intractable complexity.

DOI
10.1038/npjqi.2016.36

Related papers

Measurement-Based Quantum Computation and Symmetry-Protected Topological Order

Jacob Miller

While quantum computers can achieve dramatic speedups over the classical computers familiar to us, identifying the origin of this quantum advantage in physical systems remains a major goal of quantum information science. A useful tool here is measurement-based quantum computation (MQC), a computational framework utilizing the quantum entanglement found in many-body resource states. Not all resource states are useful for quantum computation however, so an important question is what properties of many-body entanglement characterize universal resource states, which can implement any quantum computation. Many-body states are also studied in condensed matter physics, where the collective behavior of quantum many-body systems sometimes define topological phases of matter. These phases are defined by nonlocal many-body entanglement, making topologically-ordered states natural candidates for MQC. We might wonder if these topological phases could be organized as phases of quantum computation, so that every state within the phase is universal for MQC. While phases of symmetry-protected topological order (SPTO) have arisen as natural candidates, previous attempts to demonstrate an MQC-SPTO correspondence were mostly limited to nonuniversal 1D spin chains, leaving the important 2D setting wide open. In this dissertation, we explore the wide and varied connections between MQC and SPTO, and obtain new results for 1D and 2D systems. After identifying a new MQC-SPTO correspondence within 1D spin chains, we move up and explore the operational use of 2D states with two complementary forms of SPTO. We create a new Union Jack resource state, whose different form of SPTO than previous 2D resource states permits a hierarchical notion of MQC universality. This state leads us to consider an idealized model of 2D SPTO, where we show that an additional symmetry condition makes these model states form universal resources for MQC only when they have nontrivial SPTO. We finally study the intrinsic complexity of SPTO-inspired states for classically intractable sampling, and identify inherent advantages of MQC for this purpose. Our work highlights the rich complexity available in states of entangled quantum matter, providing new evidence which sharpens our understanding of the diverse connections between MQC and SPTO.

•Jan 1, 2017•0 citations

Symmetry-protected topologically ordered states for universal quantum computation

Hendrik Poulsen Nautrup, Tzu-Chieh Wei

Measurement-based quantum computation is a model for quantum information processing utilizing local measurements on suitably entangled resource states for the implementation of quantum gates. A complete characterization for universal resource states is still missing. It has been shown that symmetry-protected topological order in one dimension can be exploited for the protection of certain quantum gates in measurement-based quantum computation. In this paper we show that the two-dimensional (2D) plaquette states on arbitrary lattices exhibit nontrivial symmetry-protected topological order in terms of symmetry fractionalization and that they are universal resource states for quantum computation. Our results of the nontrivial symmetry-protected topological order on arbitrary 2D lattices are based on an extension of the recent construction by Chen et al. [Phys. Rev. B 87, 155114 (2013)] on the square lattice.

arXiv:1509.02947•Physical Review A•Nov 9, 2015•34 citations

Qudit quantum computation on matrix product states with global symmetry

Dongsheng Wang, David T. Stephen, Robert Raussendorf

Resource states that contain nontrivial symmetry-protected topological order are identified for universal single-qudit measurement-based quantum computation. Our resource states fall into two classes: one as the qudit generalizations of the one-dimensional qubit cluster state, and the other as the higher-symmetry generalizations of the spin-1 Affleck-Kennedy-Lieb-Tasaki (AKLT) state, namely, with unitary, orthogonal, or symplectic symmetry. The symmetry in cluster states protects information propagation (identity gate), while the higher symmetry in AKLT-type states enables nontrivial gate computation. This work demonstrates a close connection between measurement-based quantum computation and symmetry-protected topological order.

arXiv:1609.07174•Physical Review A•Mar 9, 2017•33 citations

Latent Computational Complexity of Symmetry-Protected Topological Order with Fractional Symmetry

Jacob Miller, Akimasa Miyake

An emerging insight is that ground states of symmetry-protected topological orders (SPTOs) possess latent computational complexity in terms of their many-body entanglement. By introducing a fractional symmetry of SPTO, which requires the invariance under 3-colorable symmetries of a lattice, we prove that every renormalization fixed-point state of 2D (Z_{2})^{m} SPTO with fractional symmetry can be utilized for universal quantum computation using only Pauli measurements, as long as it belongs to a nontrivial 2D SPTO phase. Our infinite family of fixed-point states may serve as a base model to demonstrate the idea of a "quantum computational phase" of matter, whose states share universal computational complexity ubiquitously.

arXiv:1612.08135•Physical Review Letters•Apr 26, 2018•30 citations

Phase transitions in ( 2 + 1 ) D subsystem-symmetric monitored quantum circuits

Cole Kelson-Packer, Akimasa Miyake

The interplay of unitary evolution and projective measurements is a modern interest in the study of many-body entanglement. On the one hand, the competition between these two processes leads to the recently discovered measurement-induced phase transition (MIPT). On the other hand, measurement-based quantum computation (MBQC) is a well-known computational paradigm where measurements simulate unitary evolution by utilizing the entanglement of special resources such as the two-dimensional (2D) cluster state. The entanglement properties enabling MBQC may be attributed to symmetry-protected topological (SPT) orders, particularly subsystem-symmetry-protected topological (SSPT) orders. It was recently found that the one-dimensional cluster state may be associated with an SPT phase in random circuits respecting a global ${\mathbb{Z}}_{2}\ifmmode\times\else\texttimes\fi{}{\mathbb{Z}}_{2}$ symmetry, and furthermore that all phase transitions in this scenario belong to the same universality class. As resources with greater computational power feature greater symmetry, it is fruitful to investigate further any relationship between levels of symmetry in MIPTs and MBQC. In this paper we investigate MIPTs on a torus with three levels of symmetry-respecting unitary evolution interspersed by measurements. Although we find two area-law phases and one volume-law phase with distinct entanglement structures for each ensemble, the phase transition from the volume-law phase to the area-law phase associated with the 2D SSPT cluster state has variable correlation length exponent $\ensuremath{\nu}$. Whereas $\ensuremath{\nu}\ensuremath{\approx}0.90$ for unconstrained Clifford unitaries and $\ensuremath{\nu}\ensuremath{\approx}0.83$ for globally symmetric Cliffords, subsystem-symmetric Cliffords feature a much smaller value $\ensuremath{\nu}\ensuremath{\approx}0.38$. We discuss how these distinct $\ensuremath{\nu}$'s quantify spacetime response scales where quantum information is manipulated by single-qubit measurements as in MBQC.

arXiv:2407.18340•Physical review. B./Physical review. B•Feb 4, 2025•1 citation

Computational universality of symmetry-protected topologically ordered cluster phases on 2D Archimedean lattices

Austin K. Daniel, Rafael N. Alexander, Akimasa Miyake

What kinds of symmetry-protected topologically ordered (SPTO) ground states can be used for universal measurement-based quantum computation in a similar fashion to the 2D cluster state? 2D SPTO states are classified not only by global on-site symmetries but also by subsystem symmetries, which are fine-grained symmetries dependent on the lattice geometry. Recently, all states within so-called SPTO cluster phases on the square and hexagonal lattices have been shown to be universal, based on the presence of subsystem symmetries and associated structures of quantum cellular automata. Motivated by this observation, we analyze the computational capability of SPTO cluster phases on all vertex-translative 2D Archimedean lattices. There are four subsystem symmetries here called ribbon, cone, fractal, and 1-form symmetries, and the former three are fundamentally in one-to-one correspondence with three classes of Clifford quantum cellular automata. We conclude that nine out of the eleven Archimedean lattices support universal cluster phases protected by one of the former three symmetries, while the remaining lattices possess 1-form symmetries and have a different capability related to error correction.

arXiv:1907.13279•Quantum•Feb 10, 2020•46 citations
Abstract Measurement-based quantum computation (MQC) is a paradigm for studying quantum computation using many-body entanglement and single-qubit measurements. Although MQC has inspired wide-ranging discoveries throughout quantum information, our understanding of the general principles underlying MQC seems to be biased by its historical reliance upon the archetypal 2D cluster state. Here we utilise recent advances in the subject of symmetry-protected topological order (SPTO) to introduce a novel MQC resource state, whose physical and computational behaviour differs fundamentally from that of the cluster state. We show that, in sharp contrast to the cluster state, our state enables universal quantum computation using only measurements of single-qubit Pauli X , Y , and Z operators. This novel computational feature is related to the ‘genuine’ 2D SPTO possessed by our state, and which is absent in the cluster state. Our concrete connection between the latent computational complexity of many-body systems and macroscopic quantum orders may find applications in quantum many-body simulation for benchmarking classically intractable complexity.
While quantum computers can achieve dramatic speedups over the classical computers familiar to us, identifying the origin of this quantum advantage in physical systems remains a major goal of quantum information science. A useful tool here is measurement-based quantum computation (MQC), a computational framework utilizing the quantum entanglement found in many-body resource states. Not all resource states are useful for quantum computation however, so an important question is what properties of many-body entanglement characterize universal resource states, which can implement any quantum computation. Many-body states are also studied in condensed matter physics, where the collective behavior of quantum many-body systems sometimes define topological phases of matter. These phases are defined by nonlocal many-body entanglement, making topologically-ordered states natural candidates for MQC. We might wonder if these topological phases could be organized as phases of quantum computation, so that every state within the phase is universal for MQC. While phases of symmetry-protected topological order (SPTO) have arisen as natural candidates, previous attempts to demonstrate an MQC-SPTO correspondence were mostly limited to nonuniversal 1D spin chains, leaving the important 2D setting wide open. In this dissertation, we explore the wide and varied connections between MQC and SPTO, and obtain new results for 1D and 2D systems. After identifying a new MQC-SPTO correspondence within 1D spin chains, we move up and explore the operational use of 2D states with two complementary forms of SPTO. We create a new Union Jack resource state, whose different form of SPTO than previous 2D resource states permits a hierarchical notion of MQC universality. This state leads us to consider an idealized model of 2D SPTO, where we show that an additional symmetry condition makes these model states form universal resources for MQC only when they have nontrivial SPTO. We finally study the intrinsic complexity of SPTO-inspired states for classically intractable sampling, and identify inherent advantages of MQC for this purpose. Our work highlights the rich complexity available in states of entangled quantum matter, providing new evidence which sharpens our understanding of the diverse connections between MQC and SPTO.
Measurement-based quantum computation is a model for quantum information processing utilizing local measurements on suitably entangled resource states for the implementation of quantum gates. A complete characterization for universal resource states is still missing. It has been shown that symmetry-protected topological order in one dimension can be exploited for the protection of certain quantum gates in measurement-based quantum computation. In this paper we show that the two-dimensional (2D) plaquette states on arbitrary lattices exhibit nontrivial symmetry-protected topological order in terms of symmetry fractionalization and that they are universal resource states for quantum computation. Our results of the nontrivial symmetry-protected topological order on arbitrary 2D lattices are based on an extension of the recent construction by Chen et al. [Phys. Rev. B 87, 155114 (2013)] on the square lattice.
Resource states that contain nontrivial symmetry-protected topological order are identified for universal single-qudit measurement-based quantum computation. Our resource states fall into two classes: one as the qudit generalizations of the one-dimensional qubit cluster state, and the other as the higher-symmetry generalizations of the spin-1 Affleck-Kennedy-Lieb-Tasaki (AKLT) state, namely, with unitary, orthogonal, or symplectic symmetry. The symmetry in cluster states protects information propagation (identity gate), while the higher symmetry in AKLT-type states enables nontrivial gate computation. This work demonstrates a close connection between measurement-based quantum computation and symmetry-protected topological order.
An emerging insight is that ground states of symmetry-protected topological orders (SPTOs) possess latent computational complexity in terms of their many-body entanglement. By introducing a fractional symmetry of SPTO, which requires the invariance under 3-colorable symmetries of a lattice, we prove that every renormalization fixed-point state of 2D (Z_{2})^{m} SPTO with fractional symmetry can be utilized for universal quantum computation using only Pauli measurements, as long as it belongs to a nontrivial 2D SPTO phase. Our infinite family of fixed-point states may serve as a base model to demonstrate the idea of a "quantum computational phase" of matter, whose states share universal computational complexity ubiquitously.
The interplay of unitary evolution and projective measurements is a modern interest in the study of many-body entanglement. On the one hand, the competition between these two processes leads to the recently discovered measurement-induced phase transition (MIPT). On the other hand, measurement-based quantum computation (MBQC) is a well-known computational paradigm where measurements simulate unitary evolution by utilizing the entanglement of special resources such as the two-dimensional (2D) cluster state. The entanglement properties enabling MBQC may be attributed to symmetry-protected topological (SPT) orders, particularly subsystem-symmetry-protected topological (SSPT) orders. It was recently found that the one-dimensional cluster state may be associated with an SPT phase in random circuits respecting a global ${\mathbb{Z}}_{2}\ifmmode\times\else\texttimes\fi{}{\mathbb{Z}}_{2}$ symmetry, and furthermore that all phase transitions in this scenario belong to the same universality class. As resources with greater computational power feature greater symmetry, it is fruitful to investigate further any relationship between levels of symmetry in MIPTs and MBQC. In this paper we investigate MIPTs on a torus with three levels of symmetry-respecting unitary evolution interspersed by measurements. Although we find two area-law phases and one volume-law phase with distinct entanglement structures for each ensemble, the phase transition from the volume-law phase to the area-law phase associated with the 2D SSPT cluster state has variable correlation length exponent $\ensuremath{\nu}$. Whereas $\ensuremath{\nu}\ensuremath{\approx}0.90$ for unconstrained Clifford unitaries and $\ensuremath{\nu}\ensuremath{\approx}0.83$ for globally symmetric Cliffords, subsystem-symmetric Cliffords feature a much smaller value $\ensuremath{\nu}\ensuremath{\approx}0.38$. We discuss how these distinct $\ensuremath{\nu}$'s quantify spacetime response scales where quantum information is manipulated by single-qubit measurements as in MBQC.
What kinds of symmetry-protected topologically ordered (SPTO) ground states can be used for universal measurement-based quantum computation in a similar fashion to the 2D cluster state? 2D SPTO states are classified not only by global on-site symmetries but also by subsystem symmetries, which are fine-grained symmetries dependent on the lattice geometry. Recently, all states within so-called SPTO cluster phases on the square and hexagonal lattices have been shown to be universal, based on the presence of subsystem symmetries and associated structures of quantum cellular automata. Motivated by this observation, we analyze the computational capability of SPTO cluster phases on all vertex-translative 2D Archimedean lattices. There are four subsystem symmetries here called ribbon, cone, fractal, and 1-form symmetries, and the former three are fundamentally in one-to-one correspondence with three classes of Clifford quantum cellular automata. We conclude that nine out of the eleven Archimedean lattices support universal cluster phases protected by one of the former three symmetries, while the remaining lattices possess 1-form symmetries and have a different capability related to error correction.