notesum.ai

Published at October 31

Interactive proofs for verifying (quantum) learning and testing

quant-ph

cs.CC

cs.DS

cs.LG

Released Date: October 31, 2024

Authors: Matthias C. Caro¹, Jens Eisert², Marcel Hinsche², Marios Ioannou², Alexander Nietner², Ryan Sweke³

Aff.: ¹Department of Computer Science, University of Warwick, UK; ²Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Berlin, Germany; ³IBM Quantum, Almaden Research Center, San Jose, CA, USA

Arxiv: http://arxiv.org/abs/2410.23969v1

	$\begin{matrix}\text{Interactive proof}\\ \text{(quantum comm.)}\end{matrix}$	$\begin{matrix}\text{Interactive proof}\\ \text{(classical comm.)}\end{matrix}$	$\begin{matrix}\text{Coherent}\\ \text{measurements}\end{matrix}$	$\begin{matrix}\text{Incoherent}\\ \text{measurements}\end{matrix}$
Purity testing	$\begin{matrix}\mathcal{O}(1)\\ \text{(Theorem~{}\ref{theorem:interactive-purity-testing-black-box-intro-% version})}\end{matrix}$	$\begin{matrix}\Omega(\sqrt{d})\\ \text{(Corollary~{}\ref{cor:no-go-delegating-memory})}\end{matrix}$	$\begin{matrix}\mathcal{O}(1)\\ \text{\cite[cite]{[\@@bibref{}{chen2022exponential}{}{}]}}\end{matrix}$	$\begin{matrix}\Omega(\sqrt{d})\\ \text{\cite[cite]{[\@@bibref{}{chen2022exponential}{}{}]}}\end{matrix}$
$\begin{matrix}\text{Quantum}\\ \text{state tomography}\end{matrix}$	$\begin{matrix}\mathcal{O}(d\varepsilon^{-2})\\ \text{(Theorem~{}\ref{theorem:interactive-state-tomography-intro-version})}% \end{matrix}$	$\begin{matrix}\Omega(d^{3/2}\varepsilon^{-2})\\ \text{(Corollary~{}\ref{cor:no-advantage-qst})}\end{matrix}$	$\begin{matrix}\Omega(d^{2}\varepsilon^{-2})\\ \text{\cite[cite]{[\@@bibref{}{odonnellEfficientQuantumTomography2017}{}{}]}}% \end{matrix}$	$\begin{matrix}\Omega(d^{3}\varepsilon^{-2})\\ \text{\cite[cite]{[\@@bibref{}{haah2016sample}{}{}]}}\end{matrix}$
$\begin{matrix}\text{Agnostic}\\ \text{rank-$k$ tomography}\end{matrix}$	$\begin{matrix}\mathcal{O}(k^{2}\varepsilon^{-4})\\ \text{(Theorem~{}\ref{theorem:agnostic-rank-k-tomography})}\end{matrix}$	?	$\begin{matrix}\widetilde{\Omega}(dk)\\ \text{\cite[cite]{[\@@bibref{}{odonnell2016efficient}{}{}]}}\end{matrix}$	?
$\begin{matrix}\text{Agnostic}\\ \text{stabilizer learning}\end{matrix}$	$\begin{matrix}\mathcal{O}(\varepsilon^{-2})\\ \text{(Theorem~{}\ref{theorem:agnostic-stabilizer-state-learning-intro-version% })}\end{matrix}$	$\begin{matrix}\Omega(\sqrt{n})\\ \text{(\lx@cref{creftypecap~refnum}{corollary:no-go-stabilizer-testing})}\end{matrix}$	$\begin{matrix}\Theta(n)\\ \text{(via~{}\cite[cite]{[\@@bibref{}{arunachalam2023optimal}{}{}]})}\end{matrix}$	$\begin{matrix}\Theta(n^{2})\\ \text{(via~{}\cite[cite]{[\@@bibref{}{arunachalam2023optimal}{}{}]})}\end{matrix}$