Quantum State Reduction for Universal Measurement Based Computation

Xie Chen, Runyao Duan, Zhengfeng Ji, Bei ZengPhysical 2010 · DOI · arXiv

Abstract

Measurement-based quantum computation (MBQC), which requires only single-particle measurements on a universal resource state to achieve the full power of quantum computing, has been recognized as one of the most promising models for the physical realization of quantum computers. Despite considerable progress in the past decade, it remains a great challenge to search for new universal resource states with naturally occurring Hamiltonians and to better understand the entanglement structure of these kinds of states. Here we show that most of the resource states currently known can be reduced to the cluster state, the first known universal resource state, via adaptive local measurements at a constant cost. This new quantum state reduction scheme provides simpler proofs of universality of resource states and opens up plenty of space to the search of new resource states.

Introduction

In Measurement-Based Quantum Computation (MBQC), computation is driven not by gates, but by a sequence of single-particle measurements performed on a highly entangled "resource state." While the cluster state is the standard resource for this model, it is notoriously difficult to find in nature, as it rarely appears as a unique ground state of simple, two-body Hamiltonians.

Researchers have identified other universal states, such as the AKLT state, which are more physically realistic. However, proving their universality has traditionally required mathematically intensive Tensor Network formalisms (MPS/PEPS). This paper addresses two primary challenges: simplifying the proofs of universality for known states and establishing a framework to discover new, naturally occurring resource states.

Methodology: Quantum State Reduction

The authors introduce Quantum State Reduction, a framework analogous to reduction in complexity theory. If a complex state (State A) can be transformed into a known universal state (State B) using local operations, then State A is proven to be at least as computationally powerful as State B.

Adaptive Local Measurements and Tabular MPS

The core of this reduction involves using specific measurement schemes to strip away the "extra" complexity of a state. To manage this, the authors introduce a tabular bookkeeping method for Matrix Product States (MPS). By representing the defining matrices of a state in a table, they can visualize how local operations manipulate the underlying entanglement structure without heavy notation.

Tabular representation of Matrix Product States (MPS) illustrating the step-by-step reduction of complex operator sets to simpler target forms.

Additionally, for general "quantum wires," the framework employs non-projective measurements (filtering) to steer the state toward the target cluster state, even when the initial entanglement is disordered.

Key Insights and Results

The "Disguised" Cluster State

A central insight of this work is that many seemingly distinct resource states are actually cluster states in disguise. By applying the correct local measurements, the auxiliary complexity can be removed at a constant cost—meaning the number of particles lost does not scale with the system size.

Geometry-Preserving Reductions

Unlike previous proof methods, state reduction respects the lattice geometry of the resource. A 1D chain reduces to a 1D cluster state, while a 2D lattice reduces to a 2D cluster state. This geometric consistency is vital because 2D connectivity is a prerequisite for full-power universal quantum computing.

A 2D lattice geometry illustrating how complex physical systems can be mapped onto universal resource states through local connections.

Universal Applications

The framework was applied to several established models:

  • AKLT State: The authors provided a clean summary of its universality, reducing it to a 1D cluster state via a simple alternating measurement pattern.
  • 2D Resources: They demonstrated that 2D resources built from "weaving" quantum wires can be reduced to 2D cluster states.
  • New Discoveries: The streamlined nature of the framework allowed for the discovery of two entirely new families of universal resource states (deformations of the AKLT state).

Conclusion and Future Work

While the quantum state reduction framework is robust, some challenges remain. The authors note that certain states, such as the first toric code example, have not yet been successfully reduced to a 2D cluster state using this specific method. Future research will focus on extending this logic beyond MPS/PEPS models and moving toward experimental realization in physical systems like trapped ions or cold atoms.

Summary updated

Abstract

Measurement based quantum computation, which requires only single particle measurements on a universal resource state to achieve the full power of quantum computing, has been recognized as one of the most promising models for the physical realization of quantum computers. Despite considerable progress in the past decade, it remains a great challenge to search for new universal resource states with naturally occurring Hamiltonians and to better understand the entanglement structure of these kinds of states. Here we show that most of the resource states currently known can be reduced to the cluster state, the first known universal resource state, via adaptive local measurements at a constant cost. This new quantum state reduction scheme provides simpler proofs of universality of resource states and opens up plenty of space to the search of new resource states.
BibTeX
@inproceedings{chen2010quantum,
  author = {Xie Chen and Runyao Duan and Zhengfeng Ji and Bei Zeng},
  title = {{Quantum State Reduction for Universal Measurement Based Computation}},
  booktitle = {Physical},
  year = {2010},
  doi = {10.1103/physrevlett.105.020502},
}

Loading related content...

Figure