10 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…
Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss
Rene Allerstorfer, Andreas Bluhm, Harry Buhrman +4
Signal loss poses a significant threat to the security of quantum cryptography when the chosen protocol lacks loss-tolerance. In quantum position verification (QPV) protocols, even…
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…
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
Harry Buhrman, Sevag Gharibian, Zeph Landau +3
We present an extremely simple polynomial-space exponential-time -approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomia…
Formal Framework for Quantum Advantage
Harry Buhrman, Niklas Galke, Konstantinos Meichanetzidis
Motivated by notions of quantum heuristics and by average-case rather than worst-case algorithmic analysis, we define quantum computational advantage in terms of individual problem…