7 papers
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…
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…
An iterated random function with Lipschitz number one
Aaron Abrams, Henry Landau, Zeph Landau +2
Consider the set of functions on . Define a Markov process that starts with a point and continues with $x_{k+1}=f_{θ_{k+1}}(x_{k}…
Evasive Random Walks and the Clairvoyant Demon
Aaron Abrams, Henry Landau, Zeph Landau +2
A pair of random walks on the vertices of a graph is {\it successful} if two tokens can be scheduled (moving only one token at a time) to travel along and witho…
Optimal estimators for threshold-based quality measures
Aaron Abrams, Sandy Ganzell, Henry Landau +3
We consider a problem in parametric estimation: given samples from an unknown distribution, we want to estimate which distribution, from a given one-parameter family, produced…
Learning the closest product state
Ainesh Bakshi, John Bostanci, William Kretschmer +5
We study the problem of finding a (pure) product state with optimal fidelity to an unknown -qubit quantum state , given copies of . This is a basic instance of a fundame…