Andris Ambainis

Andris Ambainis

Auto-generated profile, based on publicly available information

Andris Ambainis

Faculty of Computing University of Latvia

Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 November 2010 in arXiv
Verified
Preprint
Open access
PDF file
AAAndris Ambainis
Andris Ambainis
We present two new quantum algorithms. Our first algorithm is a generalization of amplitude amplification to the case when parts of the quantum algorithm that is being amplified stop at different times. Our second algorithm uses the first algorithm to improve the running time of Harrow et al. algorithm for solving systems of linear equations from O(kappa^2 log N) to O(kappa log^3 kappa log N) where \kappa is the condition number of the system of equations.

9 May 2014 in computational complexity
Verified
Journal Article
Closed access
PDF file
AAAndris Ambainis
Andris Ambainis
RWRonald de Wolf
Ronald de Wolf

23 July 2015
Verified
Book Chapter
Closed access
PDF file
AAAndris Ambainis
Andris Ambainis

3 October 2025 in computational complexity
Verified
Journal Article
Closed access
PDF file
AAAndris Ambainis
Andris Ambainis
ABAleksandrs Belovs
Aleksandrs Belovs

4 July 2018 in arXiv
Verified
Preprint
Open access
PDF file
AAAndris Ambainis
Andris Ambainis
AYAbuzer Yakaryılmaz
Abuzer Yakaryılmaz
Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity

11 May 2023 in arXiv
Verified
Preprint
Open access
PDF file
AAAndris Ambainis
Andris Ambainis
ABAleksandrs Belovs
Aleksandrs Belovs
While it is known that there is at most a polynomial separation between quantum query complexity and the polynomial degree for total functions, the precise relationship between the two is not clear for partial functions. In this paper, we demonstrate an exponential separation between exact polynomial degree and approximate quantum query complexity for a partial Boolean function. For an unbounded alphabet size, we have a constant versus polynomial separation.