9 papers
Permutation tests for quantum state identity
Harry Buhrman, Dmitry Grinko, Philip Verduyn Lunel +1
The quantum analogue of the equality function, known as the quantum state identity problem, is the task of deciding whether unknown quantum states are equal or unequal, given t…
Provable and Verifiable Quantum Advantage in Sample Complexity
Marcello Benedetti, Harry Buhrman, Jordi Weggemans
Consider a fixed universe of elements and the uniform distribution over elements of some subset of size . Given samples from this distribution, the task of complement sa…
Assessing fault-tolerant quantum advantage for -SAT with structure
Martijn Brehm, Jordi Weggemans
For many problems, quantum algorithms promise speedups over their classical counterparts. However, these results predominantly rely on asymptotic worst-case analysis, which overloo…
Unconditional and exponentially large violation of classicality
Marcello Benedetti, Gabriel Marin-Sanchez, Jordi Weggemans +2
Testing the predictions of quantum mechanics has been one of the main experimental endeavors for decades. Recent advancements in technology led to a number of demonstrations which…
Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
Harry Buhrman, Jonas Helsen, Jordi Weggemans
We define a general formulation of quantum PCPs, which captures adaptivity and multiple unentangled provers, and give a detailed construction of the quantum reduction to a local Ha…
Lower Bounds for Unitary Property Testing with Proofs and Advice
Jordi Weggemans
In unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary and has to decide whether it satisfies some property. We propo…