The model of interactive oracle proofs (IOP) generalizes the notion of probabilistically checkable proof (PCP), in which a static proof is verified probabilistically by querying a small number of bits, to the interactive setting: a polynomial-time verifier interacts with an unbounded prover, but is restricted to only reading a small number of bits, in total, from the messages sent by the prover. IOPs provide a relaxed setting in which to study local probabilistic verification. They have proved instrumental in devising efficient methods for verification through subsequent compilation into non-interactive or succinct protoocls. We study a quantum analogue of interactive oracle proofs (qIOP) in which the verifier and communication are both allowed to be quantum; yet the verifier is restricted to perform measurements only on a small number of qubits received from the prover. Our main result is a qIOP for any language in QMA, in which the total communication is polynomial but the verifier only reads a polylogarithmic number of qubits in total. The protocol has completeness parameter exponentially close to 1 and soundness bounded away from 1 by a constant. In the absence of a quantum PCP theorem, this provides the first information-theoretically sound local and robust characterization of QMA, albeit interactive. Previous works in the information-theoretic setting either considered two isolated but entangled quantum provers or quantum verifiers whose effort in a single round is small but remains polynomial when aggregated across all rounds of the protocol. Our protocol combines the use of a quantum locally testable code (LTC) with classical techniques, notably probabilistically checkable proofs of proximity (PCPP). We avoid the necessity for complex multi-qubit tests employed in other settings by leveraging the local indistinguishability property of the quantum LTC.

We study the problem of interpolating a noisy Fourier-sparse signal in the time duration $[0, T]$ from noisy samples in the same range, where the ground truth signal can be any k-Fourier-sparse signal with band-limit $[-F, F]$. Our main result is an efficient Fourier Interpolation algorithm that improves the previous best algorithm by [Chen, Kane, Price, and Song, FOCS 2016] in the following three aspects:•The sample complexity is improved from $\widetilde{O}\left(k^{51}\right)$ to $\widetilde{O}\left(k^{4}\right)$.•The time complexity is improved from $\widetilde{O}\left(k^{10 \omega+40}\right)$ to $\widetilde{O}\left(k^{4 \omega}\right)$.•The output sparsity is improved from $\widetilde{O}\left(k^{10}\right)$ to $\widetilde{O}\left(k^{4}\right)$. Here, $\omega$ denotes the exponent of fast matrix multiplication. The state-of-the-art sample complexity of this problem is $\sim k^{4}$, but was only known to be achieved by an exponential-time algorithm. Our algorithm uses the same number of samples but has a polynomial runtime, laying the groundwork for an efficient Fourier Interpolation algorithm.The centerpiece of our algorithm is a new spectral analysis tool-the Signal Equivalent Method-which utilizes the structure of Fourier signals to establish nearly-optimal energy properties, and is the key for efficient and accurate frequency estimation. We use this method, along with a new sufficient condition for frequency recovery (a new high SNR band condition), to design a cheap algorithm for estimating “significant” frequencies within a narrow range. Together with a signal estimation algorithm, we obtain a new Fourier Interpolation algorithm for reconstructing the ground-truth signal.

For learned image compression, the autoregressive context model is proved effective in improving the rate-distortion (RD) performance. Because it helps remove spatial redundancies among latent representations. However, the decoding process must be done in a strict scan order, which breaks the parallelization. We propose a parallelizable checkerboard context model (CCM) to solve the problem. Our two-pass checkerboard context calculation eliminates such limitations on spatial locations by re-organizing the decoding order. Speeding up the decoding process more than 40 times in our experiments, it achieves significantly improved computational efficiency with almost the same rate-distortion performance. To the best of our knowledge, this is the first exploration on parallelization-friendly spatial context model for learned image compression.