626 citations · 636 across the 11 of their papers we have counts for
13 papers
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…
Quantum Catalytic Space
Harry Buhrman, Marten Folkertsma, Ian Mertz +4
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation…
Towards experimental demonstration of quantum position verification using true single photons
Kirsten Kanneworff, Mio Poortvliet, Dirk Bouwmeester +6
The geographical position can be a good credential for authentication of a party, this is the basis of position-based cryptography - but classically this cannot be done securely wi…
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…
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…
Beating the natural Grover bound for low-energy estimation and state preparation
Harry Buhrman, Sevag Gharibian, Zeph Landau +3
Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this work, we give quantum algorithms which, given any -body Ha…
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…
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…
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…
Clean quantum and classical communication protocols
Harry Buhrman, Matthias Christandl, Christopher Perry +1
By how much must the communication complexity of a function increase if we demand that the parties not only correctly compute the function but also return all registers (other than…
Non-locality and Communication Complexity
Harry Buhrman, Richard Cleve, Serge Massar +1
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles, like the superposition principle, e…