48 citations · 70 across the 12 of their papers we have counts for
15 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…
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…
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…
Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
Jordi Weggemans, Marten Folkertsma, Chris Cade
We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem, which we call 'Guidable Local Hamiltonian' problems. Unlike their guided counterparts, thes…
Improved Hardness Results for the Guided Local Hamiltonian Problem
Chris Cade, Marten Folkertsma, Sevag Gharibian +4
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum alg…
Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
Chris Cade, Marten Folkertsma, Jordi Weggemans
Recently it was shown that the so-called guided local Hamiltonian problem -- estimating the smallest eigenvalue of a -local Hamiltonian when provided with a description of a qua…
Quantum Algorithms for Community Detection and their Empirical Run-times
Chris Cade, Marten Folkertsma, Ido Niesen +1
We apply our recent work on empirical estimates of quantum speedups to the practical task of community detection in complex networks. We design several quantum variants of a popula…
Quantifying Grover speed-ups beyond asymptotic analysis
Chris Cade, Marten Folkertsma, Ido Niesen +1
Run-times of quantum algorithms are often studied via an asymptotic, worst-case analysis. Whilst useful, such a comparison can often fall short: it is not uncommon for algorithms w…
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
Jordi R. Weggemans, Alexander Urech, Alexander Rausch +6
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits, which constitute a natural platform for such non-binary problems…
Tunable critical field in Rashba superconductor thin-films
L. A. B. Olde Olthof, J. R. Weggemans, G. Kimbell +2
The upper critical field in type II superconductors is limited by the Pauli paramagnetic limit. In superconductors with strong Rashba spin-orbit coupling this limit can be overcome…