We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given $n$ $d$-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with con
stant margin runs in $tilde{O}(n+d)$ time. We design sublinear quantum algorithms for the same task running in $tilde{O}(sqrt{n} +sqrt{d})$ time, a quadratic improvement in both $n$ and $d$. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines. As a side result, we also give sublinear quantum algorithms for approximating the equilibria of $n$-dimensional matrix zero-sum games with optimal complexity $tilde{Theta}(sqrt{n})$.
This paper presents an efficient parallel approximation scheme for a new class of min-max problems. The algorithm is derived from the matrix multiplicative weights update method and can be used to find near-optimal strategies for competitive two-part
y classical or quantum interactions in which a referee exchanges any number of messages with one party followed by any number of additional messages with the other. It considerably extends the class of interactions which admit parallel solutions, demonstrating for the first time the existence of a parallel algorithm for an interaction in which one party reacts adaptively to the other. As a consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG(2), SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a specific class of semidefinite programs whose feasible region consists of lists of semidefinite matrices that satisfy a transcript-like consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP=PSPACE.
The Non-Identity Check problem asks whether a given a quantum circuit is far away from the identity or not. It is well known that this problem is QMA-Complete cite{JWB05}. In this note, it is shown that the Non-Identity Check problem remains QMA-Comp
lete for circuits of short depth. Specifically, we prove that for constant depth quantum circuit in which each gate is given to at least $Omega(log n)$ bits of precision, the Non-Identity Check problem is QMA-Complete. It also follows that the hardness of the problem remains for polylogarithmic depth circuit consisting of only gates from any universal gate set and for logarithmic depth circuit using some specific universal gate set.
