9 papers · 1 filter
Quantum Separability in Polynomial Time
Giulio Malavolta
The quantum separability problem asks whether a bipartite density matrix is separable or is -far from every separable state. We give a randomized polynomial-time algorithm for…
MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)
Andrea Coladangelo, Ruta Jawale, Dakshita Khurana +2
The MPC-in-the-head technique (Ishai et al., STOC 2007) is a celebrated method to build zero-knowledge protocols with desirable theoretical properties and high practical efficiency…
A Modular Approach to Succinct Arguments for QMA
James Bartusek, Jiahui Liu, Giulio Malavolta
Succinct argument systems are of central importance to modern crytpography, enabling the efficient verification of computational claims. In the classical setting, Kilian (STOC 92)…
A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
David Cui, Giulio Malavolta, Arthur Mehta +5
Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work…
The Knowledge Complexity of Quantum Problems
Giulio Malavolta
Foundational results in theoretical computer science have established that everything provable, is provable in zero knowledge. However, this assertion fundamentally assumes a class…
Computational Monogamy of Entanglement and Non-Interactive Quantum Key Distribution
Alex B. Grilo, Giulio Malavolta, Michael Walter +1
Quantum key distribution (QKD) enables Alice and Bob to exchange a secret key over a public, untrusted quantum channel. Compared to classical key exchange, QKD achieves everlasting…