2 citations · 2 across the 2 of their papers we have counts for
7 papers · 1 filter
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…
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…
Classical versus quantum queries in quantum PCPs with classical proofs
Harry Buhrman, François Le Gall, Jordi Weggemans
We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for quantum queries to a polynomially-sized classical proof ($\mat…
Finding quantum partial assignments by search-to-decision reductions
Jordi Weggemans
In computer science, many search problems are reducible to decision problems, which implies that finding a solution is as hard as deciding whether a solution exists. A quantum anal…
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…