41 citations · 70 across the 5 of their papers we have counts for
5 papers
Merlin-Arthur Games and Stoquastic Complexity
Sergey Bravyi, Arvid J. Bessen, Barbara M. Terhal
MA is a class of decision problems for which `yes'-instances have a proof that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural comple…
Distributions of continuous-time quantum walks
Arvid J. Bessen
We study the distributions of the continuous-time quantum walk on a one-dimensional lattice. In particular we will consider walks on unbounded lattices, walks with one and two boun…
A Lower Bound for the Sturm-Liouville Eigenvalue Problem on a Quantum Computer
Arvid J. Bessen
We study the complexity of approximating the smallest eigenvalue of a univariate Sturm-Liouville problem on a quantum computer. This general problem includes the special case of so…
A Lower Bound for Quantum Phase Estimation
Arvid J. Bessen
We obtain a query lower bound for quantum algorithms solving the phase estimation problem. Our analysis generalizes existing lower bound approaches to the case where the oracle Q i…
Approximation of Various Quantum Query Types
Arvid J. Bessen
Query complexity measures the amount of information an algorithm needs about a problem to compute a solution. On a quantum computer there are different realizations of a query and…