Matthew Coudron

STOC Conference 2023 Conference Paper

Quantum Depth in the Random Oracle Model

• Atul Singh Arora
• Andrea Coladangelo
• Matthew Coudron
• Alexandru Gheorghiu
• Uttam Singh
• Hendrik Waldner

FOCS Conference 2021 Conference Paper

Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits

• Nolan J. Coble
• Matthew Coudron

We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit $C$, and any bit string $x\in\{0, 1\}^{n}$, can compute the quantity $\vert \langle x\vert C\vert 0^{\otimes n}\rangle\vert ^{2}$ to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is $\# P$ -hard to compute this same quantity to within $2^{-n^{2}}$ additive error [1], [2], and worst-case hardness results for this task date back to [3]. The previous best known algorithm for this problem used $O(2^{n^{1/3}}\text{poly}(1/\epsilon))$ time to compute probabilities to within additive error $\epsilon$ [4]. Notably, that paper, [4], included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings. To our knowledge this is the first use of the block-encoding technique in a purely classical algorithm. Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit “pieces” produced this way. We believe that the division step, which makes a novel use of block-encodings [5], together with an Inclusion-Exclusion argument to reduce error in each recursive approximation, may be of independent interest. 1 1 The full version of this paper is available at arXiv: 2012. 05460. We refer the reader to the full text for proofs of all Lemmas and Theorems.

STOC Conference 2020 Conference Paper

Computations with greater quantum depth are strictly more powerful (relative to an oracle)

• Matthew Coudron
• Sanketh Menda

STOC Conference 2014 Conference Paper

Infinite randomness expansion with a constant number of devices

• Matthew Coudron
• Henry Yuen

We present a device-independent randomness expansion protocol, involving only a constant number of non-signaling quantum devices, that achieves infinite expansion : starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is exp(--Ω( m 1/3 ))-close to uniform and secure against a quantum adversary. The only parameters which depend on the size of the input are the soundness of the protocol and the security of the output (both are inverse exponential in m ). This settles a long-standing open problem in the area of randomness expansion and device-independence. The analysis of our protocols involves overcoming fundamental challenges in the study of adaptive device-independent protocols. Our primary technical contribution is the design and analysis of device-independent protocols which are Input Secure ; that is, their output is guaranteed to be secure against a quantum eavesdropper, even if the input randomness was generated by that same eavesdropper ! The notion of Input Security may be of independent interest to other areas such as device-independent quantum key distribution.

NeurIPS Conference 2012 Conference Paper

On the Sample Complexity of Robust PCA

• Matthew Coudron
• Gilad Lerman

We estimate the sample complexity of a recent robust estimator for a generalized version of the inverse covariance matrix. This estimator is used in a convex algorithm for robust subspace recovery (i. e. , robust PCA). Our model assumes a sub-Gaussian underlying distribution and an i. i. d. ~sample from it. Our main result shows with high probability that the norm of the difference between the generalized inverse covariance of the underlying distribution and its estimator from an i. i. d. ~sample of size $N$ is of order $O(N^{-0. 5+\eps})$ for arbitrarily small $\eps>0$ (affecting the probabilistic estimate); this rate of convergence is close to one of direct covariance and inverse covariance estimation, i. e. , $O(N^{-0. 5})$. Our precise probabilistic estimate implies for some natural settings that the sample complexity of the generalized inverse covariance estimation when using the Frobenius norm is $O(D^{2+\delta})$ for arbitrarily small $\delta>0$ (whereas the sample complexity of direct covariance estimation with Frobenius norm is $O(D^{2})$). These results provide similar rates of convergence and sample complexity for the corresponding robust subspace recovery algorithm, which are close to those of PCA. To the best of our knowledge, this is the only work analyzing the sample complexity of any robust PCA algorithm.