Compare Papers

Paper 1

PropHunt: Automated Optimization of Quantum Syndrome Measurement Circuits

Joshua Viszlai, Satvik Maurya, Swamit Tannu, Margaret Martonosi, Frederic T. Chong

Year

2026

Journal

arXiv preprint

DOI

arXiv:2601.17580

arXiv

2601.17580

Fault-Tolerant Quantum Computing (FTQC) relies on Quantum Error Correction (QEC) codes to reach error rates necessary for large scale quantum applications. At a physical level, QEC codes perform parity checks on data qubits, producing syndrome information, through Syndrome Measurement (SM) circuits. These circuits define a code's logical error rate and must be run repeatedly throughout the entire program. The performance of SM circuits is therefore critical to the success of a FTQC system. While ultimately implemented as physical circuits, SM circuits have challenges that are not addressed by existing circuit optimization tools. Importantly, inside SM circuits themselves errors are expected to occur, and how errors propagate through SM circuits directly impacts which errors are detectable and correctable, defining the code's logical error rate. This is not modeled in NISQ-era tools, which instead optimize for targets such as gate depth or gate count to mitigate the chance that any error occurs. This gap leaves key questions unanswered about the expected real-world effectiveness of QEC codes. In this work we address this gap and present PropHunt, an automated tool for optimizing SM circuits for CSS codes. We evaluate PropHunt on a suite of relevant QEC codes and demonstrate PropHunt's ability to iteratively improve performance and recover existing hand-designed circuits automatically. We also propose a near-term QEC application, Hook-ZNE, which leverages PropHunt's fine-grained control over logical error rate to improve Zero-Noise Extrapolation (ZNE), a promising error mitigation strategy.

Open paper

Paper 2

The quantum smooth label cover problem is undecidable

Eric Culf, Kieran Mastel, Connor Paddock, Taro Spirig

Year

2025

Journal

arXiv preprint

DOI

arXiv:2510.03477

arXiv

2510.03477

We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige's reduction from 3SAT to 3SAT5 (STOC'96) for BCSMIP*-protocols, which may be of independent interest.

Open paper