Preprints

Complexity

Year Content Icon
H. Klauck, D. Lim The Power of One Clean Qubit in Communication Complexity.
T. Lee, T. Lee, Aleksandrs Belovs The quantum query complexity of composition with a relation.
A. Garcia-Saez, J. I. Latorre Addressing hard classical problems with Adiabatically Assisted Variational Quantum Eigensolvers.
Seth Lloyd, R.Patrick Quantum computational finance: quantum algorithm for portfolio optimization.
Ansis Rosmanis, Nathan Lindzey A Tight Lower Bound for Index Erasure.
H. Klauck, Debbie Lim The Power of One Clean Qubit in Communication Complexity.
I. Kerenidis, Alessandro Luongo Quantum classification of the MNIST dataset via Slow Feature Analysis.
Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, Antonios Varvitsiotis Vector Coloring the Categorical Product of Graphs.
Juan Miguel Arrazola, Eleni Diamanti, I. Kerenidis Quantum superiority for verifying NP-complete problems with linear optics.
Ritajit Majumdar, Saikat Basu, P. Mukhopadhyay, Susmita Sur-Kolay Error tracing in linear and concatenated quantum circuits.
P. Mukhopadhyay, Y. Qiao Sparse multivariate polynomial interpolation in the basis of Schubert polynomials.
T. Lee, T. Lee, Z.H. Wei, Ronald de Wolf Some upper and lower bounds on PSD-rank.
A.Prakash, A.Varvitsiotis Matrix factorizations of correlation matrices and applications.
J. Thompson, A.Garner, V. Vedral, M. Gu Using quantum theory to reduce the complexity of input-output processes.
A.Garner, J. Thompson, V. Vedral, M. Gu When is simpler thermodynamically better?.
R. Jain, Nisheeth K. Vishnoi, T. Lee, T. Lee A quadratically tight partition bound for classical communication complexity and query complexity.
J. I. Latorre, German Sierra Quantum Computation of Prime Number Functions.
R. Jain, P. Yao A strong direct product theorem in terms of the smooth rectangle bound.
Andrew C. Doherty, S. Wehner Convergence of SDP hierarchies for polynomial optimization on the hypersphere.
Anne Broadbent, J. Fitzsimons, Elham Kashefi QMIP = MIP*.
Matthew McKague BQP interactive proof for recursive Fourier sampling.
T. Lee, T. Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek An adversary for algorithms.
Ming Lam Leung, Yang Li, Shengyu Zhang Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models.
S. Zhang Quantum Strategic Game Theory.
I. Kerenidis, S. Zhang A quantum protocol for sampling correlated equilibria unconditionally and without a mediator.
B. Rosgen, Lorna Stewart The overlap number of a graph.