Ashley Montanaro

ACM Trans. Comput. Theory, March, 2024

2023

Quantum and classical query complexities of functions of matrices.

[BibT_eX]

[DOI]

CoRR, 2023

Quantum Majority Vote.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Quantum Algorithms for Learning a Hidden Graph.

[BibT_eX]

[DOI]

Proceedings of the 17th Conference on the Theory of Quantum Computation, 2022

2021

Quantum Random Access Codes for Boolean Functions.

[BibT_eX]

[DOI]

João F. Doriguello

Quantum, 2021

Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance.

[BibT_eX]

[DOI]

Quantum, 2021

Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit.

[BibT_eX]

[DOI]

Sami Boulebnane

CoRR, 2021

Faster quantum-inspired algorithms for solving linear systems.

[BibT_eX]

[DOI]

CoRR, 2021

2020

Quantum algorithms for learning graphs and beyond.

[BibT_eX]

[DOI]

CoRR, 2020

Quantum speedups of some general-purpose numerical optimisation algorithms.

[BibT_eX]

[DOI]

Cezar-Mihail Alexandru

Ella Bridgett-Tomkinson

CoRR, 2020

Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem.

[BibT_eX]

[DOI]

João F. Doriguello

Proceedings of the 15th Conference on the Theory of Quantum Computation, 2020

2019

Quantum speedup of branch-and-bound algorithms.

[BibT_eX]

[DOI]

CoRR, 2019

2018

Quantum-Walk Speedup of Backtracking Algorithms.

[BibT_eX]

[DOI]

Theory Comput., 2018

Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness.

[BibT_eX]

[DOI]

Chris Cade

Aleksandrs Belovs

Quantum Inf. Comput., 2018

The Quantum Complexity of Computing Schatten p-norms.

[BibT_eX]

[DOI]

Chris Cade

Proceedings of the 13th Conference on the Theory of Quantum Computation, 2018

2017

The complexity of antiferromagnetic interactions and 2D lattices.

[BibT_eX]

[DOI]

Stephen Piddock

Quantum Inf. Comput., 2017

Quantum computational supremacy.

[BibT_eX]

[DOI]

Nat., 2017

Quantum Key Search with Side Channel Advice.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2017

Quantum Pattern Matching Fast on Average.

[BibT_eX]

[DOI]

Algorithmica, 2017

Sequential measurements, disturbance and property testing.

[BibT_eX]

[DOI]

Cedric Yen-Yu Lin

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Exact Quantum Algorithms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

A Survey of Quantum Property Testing.

[BibT_eX]

[DOI]

Ronald de Wolf

Theory Comput., 2016

Complexity Classification of Local Hamiltonian Problems.

[BibT_eX]

[DOI]

Toby S. Cubitt

SIAM J. Comput., 2016

The quantum complexity of approximating the frequency moments.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2016

Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs.

[BibT_eX]

[DOI]

Dominic J. Moylett

Noah Linden

CoRR, 2016

Quantum states cannot be transmitted efficiently classically.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Extremal eigenvalues of local Hamiltonians.

[BibT_eX]

[DOI]

CoRR, 2015

Average-case complexity versus approximate simulation of commuting quantum computations.

[BibT_eX]

[DOI]

Michael J. Bremner

Dan J. Shepherd

CoRR, 2015

On Exact Quantum Query Complexity.

[BibT_eX]

[DOI]

Richard Jozsa

Graeme Mitchison

Algorithmica, 2015

2014

Quantum algorithms for search with wildcards and combinatorial group testing.

[BibT_eX]

[DOI]

Andris Ambainis

Quantum Inf. Comput., 2014

A composition theorem for decision tree complexity.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2014

2013

Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization.

[BibT_eX]

[DOI]

J. ACM, 2013

2012

The Complexity of Flood Filling Games.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2012

The quantum query complexity of learning multilinear polynomials.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2012

Almost all decision trees do not allow significant quantum speed-up.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2012

2011

Unbounded-error quantum query complexity.

[BibT_eX]

[DOI]

Harumichi Nishimura

Rudy Raymond

Theor. Comput. Sci., 2011

A new exponential separation between quantum and classical one-way communication complexity.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2011

Unentangled Quantum Proofs and their Applications.

[BibT_eX]

[DOI]

ERCIM News, 2011

Limitations on Quantum Dimensionality Reduction.

[BibT_eX]

[DOI]

Anthony J. Short

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Nonadaptive quantum query complexity.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2010

Quantum boolean functions.

[BibT_eX]

[DOI]

Tobias Osborne

Chic. J. Theor. Comput. Sci., 2010

Quantum Search with Advice.

[BibT_eX]

[DOI]

Proceedings of the Theory of Quantum Computation, Communication, and Cryptography, 2010

The Complexity of Flood Filling Games.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms, 5th International Conference, 2010

An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Quantum search of partially ordered sets.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2009

Quantum algorithms for shifted subset problems.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2009

On the communication complexity of XOR functions

[BibT_eX]

[DOI]

Tobias Osborne

CoRR, 2009

2008

A lower bound on the probability of error in quantum state discrimination.

[BibT_eX]

[DOI]

Proceedings of the 2008 IEEE Information Theory Workshop, 2008

2007

Structure, randomness and complexity in quantum computation.

[BibT_eX]

[DOI]

PhD thesis, 2007

Quantum walks on directed graphs.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2007

On the Quantum Chromatic Number of a Graph.

[BibT_eX]

[DOI]

Electron. J. Comb., 2007

A Lower Bound on Entanglement-Assisted Quantum Communication Complexity.

[BibT_eX]

[DOI]