Preprints

Complexity

Year Content Icon
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.
I. Kerenidis, S. Zhang A quantum protocol for sampling correlated equilibria unconditionally and without a mediator.
J. I. Latorre, German Sierra Quantum Computation of Prime Number Functions.
B. Rosgen, Lorna Stewart The overlap number of a graph.
S. Zhang Quantum Strategic Game Theory.
, Ming Lam Leung, Yang Li, Shengyu Zhang Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models.
T. Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek An adversary for algorithms.
Matthew McKague BQP interactive proof for recursive Fourier sampling.
, Anne Broadbent, J. Fitzsimons, Elham Kashefi QMIP = MIP*.
A.Prakash, A.Varvitsiotis Matrix factorizations of correlation matrices and applications.
R. Jain, Nisheeth K. Vishnoi, T. Lee A quadratically tight partition bound for classical communication complexity and query complexity.
, Ritajit Majumdar, Saikat Basu, P. Mukhopadhyay, Susmita Sur-Kolay Error tracing in linear and concatenated quantum circuits.
, Andrew C. Doherty, S. Wehner Convergence of SDP hierarchies for polynomial optimization on the hypersphere.
R. Jain, P. Yao A strong direct product theorem in terms of the smooth rectangle bound.
P. Mukhopadhyay, Y. Qiao Sparse multivariate polynomial interpolation in the basis of Schubert polynomials.
G. Ivanyos, Péter Kutas, Lajos Rónyai Computing explicit isomorphisms with full matrix algebras over $\mathbb{F}_q(x)$.
W.Y Suen, J. Thompson, A.Garner, V. Vedral, M. Gu The classical-quantum divergence of complexity in the Ising spin chain.
A.Garner, J. Thompson, V. Vedral, M. Gu When is simpler thermodynamically better?.
J. Thompson, A.Garner, V. Vedral, M. Gu Using quantum theory to reduce the complexity of input-output processes.
G. Ivanyos, Youming Qiao, K. V. Subrahmanyam Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics.
T. Lee, Z.H. Wei, Ronald de Wolf Some upper and lower bounds on PSD-rank.