194 citations · 1.9k across the 115 of their papers we have counts for
4 papers · 1 filter
Quantum Walks On Graphs
Dorit Aharonov, Andris Ambainis, Julia Kempe +1
We set the ground for a theory of quantum walks on graphs- the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stati…
On the class of languages recognizable by 1-way quantum finite automata
Andris Ambainis, Arnolds Kikusts, Maris Valdats
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) l…
Computing with highly mixed states
Andris Ambainis, Leonard J. Schulman, Umesh Vazirani
We consider quantum computing in the k-qubit model where the starting state of a quantum computer consists of k qubits in a pure state and n-k qubits in a maximally mixed state. We…
Quantum lower bounds by quantum arguments
Andris Ambainis
We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, w…