65 citations · 120 across the 10 of their papers we have counts for
Showing 2000Show all
3 papers · 1 filter
quant-ph2000
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…
quant-ph2000
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…
quant-ph2000
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…