Buchumschlag

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gu, Shouzhen, Wang, Lily, Kubica, Aleksander
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Quantum Physics Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Check-weight-constrained quantum codes: Bounds and examples
von: Wang, Lily, et al.
Veröffentlicht: (2026)

Hardness results for decoding the surface code with Pauli noise
von: Fischer, Alex, et al.
Veröffentlicht: (2023)

Single-shot decoding of good quantum LDPC codes
von: Gu, Shouzhen, et al.
Veröffentlicht: (2023)

Finding the disjointness of stabilizer codes is NP-complete
von: Bostanci, John, et al.
Veröffentlicht: (2021)

Quantum Max-Cut is NP hard to approximate
von: Piddock, Stephen
Veröffentlicht: (2025)

Fault-tolerant compiling of classically hard IQP circuits on hypercubes
von: Hangleiter, Dominik, et al.
Veröffentlicht: (2024)

Fault-tolerant quantum architectures based on erasure qubits
von: Gu, Shouzhen, et al.
Veröffentlicht: (2023)

Layer codes as partially self-correcting quantum memories
von: Gu, Shouzhen, et al.
Veröffentlicht: (2025)

Fast correlated decoding of transversal logical algorithms
von: Cain, Madelyn, et al.
Veröffentlicht: (2025)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
von: Mitosek, Piotr
Veröffentlicht: (2024)

Improved decoding of circuit noise and fragile boundaries of tailored surface codes
von: Higgott, Oscar, et al.
Veröffentlicht: (2022)

The 7 faces of quantum NP
von: Gharibian, Sevag
Veröffentlicht: (2023)

Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
von: He, Entong
Veröffentlicht: (2024)

An iterative transversal CNOT decoder
von: Wan, Kwok Ho, et al.
Veröffentlicht: (2024)

Optimizing quantum error correction protocols with erasure qubits
von: Gu, Shouzhen, et al.
Veröffentlicht: (2024)

BQP, meet NP: Search-to-decision reductions and approximate counting
von: Gharibian, Sevag, et al.
Veröffentlicht: (2024)

On the hardness of cloning and connections to representation theory
von: Havlíček, Vojtěch, et al.
Veröffentlicht: (2024)

Optimising quantum circuits is generally hard
von: van de Wetering, John, et al.
Veröffentlicht: (2023)

Complexity and hardness of random peaked circuits
von: Zhang, Yuxuan
Veröffentlicht: (2025)

DQC1-hardness of estimating correlation functions
von: Moulik, Subhayan Roy, et al.
Veröffentlicht: (2024)

How hard is it to verify a classical shadow?
von: Karaiskos, Georgios, et al.
Veröffentlicht: (2025)

NLTS Hamiltonians from good quantum codes
von: Anshu, Anurag, et al.
Veröffentlicht: (2022)

Exponential improvements to the average-case hardness of BosonSampling
von: Bouland, Adam, et al.
Veröffentlicht: (2024)

Exact Quantum Circuit Optimization is co-NQP-hard
von: Kjelstrøm, Adam Husted, et al.
Veröffentlicht: (2025)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
von: Rayudu, Chaithanya
Veröffentlicht: (2024)

Transversal non-Clifford gates for quantum LDPC codes on sheaves
von: Lin, Ting-Chun
Veröffentlicht: (2024)

Error correction of transversal CNOT gates for scalable surface code computation
von: Sahay, Kaavya, et al.
Veröffentlicht: (2024)

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
von: Dinur, Irit, et al.
Veröffentlicht: (2024)

Approximating the quantum value of an LCS game is RE-hard
von: Taller, Aviv, et al.
Veröffentlicht: (2025)

Uniformity testing when you have the source code
von: Canonne, Clément L., et al.
Veröffentlicht: (2024)

Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
von: Zhan, Junpeng
Veröffentlicht: (2023)

Communication Complexity is NP-hard
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Deterministic list decoding of Reed-Solomon codes
von: Chatterjee, Soham, et al.
Veröffentlicht: (2025)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
von: Morimae, Tomoyuki, et al.
Veröffentlicht: (2025)

Minimising surface-code failures using a color-code decoder
von: Benhemou, Asmae, et al.
Veröffentlicht: (2023)

Computational hardness of estimating quantum entropies via binary entropy bounds
von: Liu, Yupan
Veröffentlicht: (2026)

Classically Spoofing System Linear Cross Entropy Score Benchmarking
von: Tanggara, Andrew, et al.
Veröffentlicht: (2024)

Lifting topological codes: Three-dimensional subsystem codes from two-dimensional anyon models
von: Bridgeman, Jacob C., et al.
Veröffentlicht: (2023)

Scalable decoding protocols for fast transversal logic in the surface code
von: Turner, Mark L., et al.
Veröffentlicht: (2025)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
von: Apers, Simon, et al.
Veröffentlicht: (2021)