Cover Image

The NPA hierarchy does not always attain the commuting operator value

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fanizza, Marco, Kroell, Larissa, Mehta, Arthur, Paddock, Connor, Rochette, Denis, Slofstra, William, Zhao, Yuming
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Satisfiability problems and algebras of boolean constraint system games
by: Paddock, Connor, et al.
Published: (2023)

Two prover perfect zero knowledge for MIP*
by: Mastel, Kieran, et al.
Published: (2024)

The membership problem for constant-sized quantum correlations is undecidable
by: Fu, Honghao, et al.
Published: (2021)

Quantum delegation with an off-the-shelf device
by: Broadbent, Anne, et al.
Published: (2023)

On the undecidability of quantum channel capacities
by: Bhattacharyya, Archishna, et al.
Published: (2026)

Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy
by: Klep, Igor, et al.
Published: (2025)

Self-testing in the compiled setting via tilted-CHSH inequalities
by: Mehta, Arthur, et al.
Published: (2024)

New Approaches to Complexity via Quantum Graphs
by: Culf, Eric, et al.
Published: (2023)

Quantum circuit lower bounds in the magic hierarchy
by: Parham, Natalie
Published: (2025)

Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete
by: Hutton, Kiera, et al.
Published: (2025)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
by: Anand, Kartik, et al.
Published: (2025)

Monogamy of Nonlocal Games
by: Cui, David, et al.
Published: (2024)

Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states
by: Paddock, Connor
Published: (2022)

Satisfiability of commutative vs. non-commutative CSPs
by: Bulatov, Andrei A., et al.
Published: (2024)

Two convergent NPA-like hierarchies for the quantum bilocal scenario
by: Renou, Marc-Olivier, et al.
Published: (2022)

Existence and nonexistence of commutativity gadgets for entangled CSPs
by: Culf, Eric, et al.
Published: (2025)

Quantum polymorphism characterisation of commutativity gadgets in all quantum models
by: Culf, Eric, et al.
Published: (2026)

Whether a quantum computation employs nonlocal resources is operationally undecidable
by: Fields, Chris, et al.
Published: (2025)

Positivity is undecidable in tensor products of free algebras
by: Mehta, Arthur, et al.
Published: (2023)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
by: Gall, François Le, et al.
Published: (2023)

Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
by: Bu, Kaifeng, et al.
Published: (2023)

Approximating the quantum value of an LCS game is RE-hard
by: Taller, Aviv, et al.
Published: (2025)

Gibbs state preparation for commuting Hamiltonian: Mapping to classical Gibbs sampling
by: Hwang, Yeongwoo, et al.
Published: (2024)

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
by: Grewal, Sabee, et al.
Published: (2025)

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
by: Aldi, Marco, et al.
Published: (2024)

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
by: Gay, William, et al.
Published: (2026)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)

The Acrobatics of BQP
by: Aaronson, Scott, et al.
Published: (2021)

Pseudoentanglement Ain't Cheap
by: Grewal, Sabee, et al.
Published: (2024)

Complexity of quantum circuits via sensitivity, magic, and coherence
by: Bu, Kaifeng, et al.
Published: (2022)

Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
by: Watts, Adam Bene, et al.
Published: (2025)

Quantum Pseudorandomness and Classical Complexity
by: Kretschmer, William
Published: (2021)

Undecidability and incompleteness in quantum information theory and operator algebras
by: Goldbring, Isaac
Published: (2024)

Demonstrating Quantum Homomorphic Encryption Through Simulation
by: Ganjian, Sohrab, et al.
Published: (2024)

A bound on the quantum value of all compiled nonlocal games
by: Kulpe, Alexander, et al.
Published: (2024)

Quantum-Computable One-Way Functions without One-Way Functions
by: Kretschmer, William, et al.
Published: (2024)

Quantization of Kähler manifolds via differential operators
by: Chan, Kwokwai, et al.
Published: (2025)

Quantum Mass Production Theorems
by: Kretschmer, William
Published: (2022)

Quantum Cryptography in Algorithmica
by: Kretschmer, William, et al.
Published: (2022)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
by: Grewal, Sabee, et al.
Published: (2022)