Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2510.05557 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913135338717184 |
|---|---|
| author | Harrison, Brent Iyer, Vishnu Parekh, Ojas Thompson, Kevin Zhao, Andrew |
| author_facet | Harrison, Brent Iyer, Vishnu Parekh, Ojas Thompson, Kevin Zhao, Andrew |
| contents | Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers. A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation. Any such universal family must have unbounded entanglement width, which is equivalent to the ability to produce any circle graph state from the states in the family using only local Clifford operations, local Pauli measurements, and classical communication. Yet, it was not previously known whether or not circle graph states themselves are a universal resource. We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC (i.e., assuming $\mathsf{BQP} \neq \mathsf{BPP}$). We prove this by articulating a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This is accomplished by synthesizing a variety of techniques that allow us to handle both stabilizer states and fermionic Gaussian states at the same time. As such, we anticipate that our developments may have broader applications beyond the domain of MBQC as well. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05557 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fermionic Insights into Measurement-Based Quantum Computation: Circle Graph States Are Not Universal Resources Harrison, Brent Iyer, Vishnu Parekh, Ojas Thompson, Kevin Zhao, Andrew Quantum Physics Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers. A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation. Any such universal family must have unbounded entanglement width, which is equivalent to the ability to produce any circle graph state from the states in the family using only local Clifford operations, local Pauli measurements, and classical communication. Yet, it was not previously known whether or not circle graph states themselves are a universal resource. We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC (i.e., assuming $\mathsf{BQP} \neq \mathsf{BPP}$). We prove this by articulating a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This is accomplished by synthesizing a variety of techniques that allow us to handle both stabilizer states and fermionic Gaussian states at the same time. As such, we anticipate that our developments may have broader applications beyond the domain of MBQC as well. |
| title | Fermionic Insights into Measurement-Based Quantum Computation: Circle Graph States Are Not Universal Resources |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2510.05557 |