PaperfootJoin free

Quantum

Friday, October 21 paper

arXiv

Tight Post-Quantum Parallel Repetition for Private-Coin Arguments

Zvika Brakerski, Andrew Huang, Yael Tauman Kalai et al.

We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the…We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight exponential rate even in the…

Preprint: theory
Paper

Thursday, October 111 papers

arXiv

Exponential quantum speedup for F₃ⁿ-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

Robin Kothari, Tony Metger, Ryan O'Donnell et al.

We study vector subset sum over F₃ⁿ: given m random vectors from F₃ⁿ, find a nonempty subset that sums to zero; the smaller m, the more difficult it is to find such a…We study vector subset sum over F₃ⁿ: given m random vectors from F₃ⁿ, find a nonempty subset that sums to zero; the smaller m, the more difficult it is to find such a subset.

Preprint: method
Paper
arXiv

Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time

William Gay, Fernando Granha Jeronimo, Abhi Shukul

In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force.In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered…

Preprint: theory
Paper
arXiv

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén et al.

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm…We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices.

Preprint: method
Paper
arXiv

NLTM Hamiltonians from gauged sheaf quantum locally testable codes

Fuchuan Wei, Zhengyi Han, Zimu Li et al.

Understanding the complexity of low-energy quantum states is a central problem in quantum complexity theory and many-body physics.Understanding the complexity of low-energy quantum states is a central problem in quantum complexity theory and many-body physics.

Preprint: theory
Paper
arXiv

Unconditional quantum advantage with noisy planar architectures

Libor Caha, Robert Koenig, Louis Paletta

We consider quantum devices restricted to local operations in 2D and subject to local stochastic noise below a constant threshold.We consider quantum devices restricted to local operations in 2D and subject to local stochastic noise below a constant threshold. We show that such circuits are computationally more powerful than AC0-circuits, i.e., noise-free…

Preprint: theory
Paper
arXiv

Natural Barriers to Quantum Extraction: On the Post-Quantum (In)security of (O)EKE and Masny-Rindal OT

James Bartusek, Jake Januzelli

Encrypted key exchange (EKE), introduced by Bellovin and Merritt (IEEE S&P 1992), and Masny-Rindal OT, introduced by Masny and Rindal (ACM CCS 2019), are highly-efficient…Encrypted key exchange (EKE), introduced by Bellovin and Merritt (IEEE S&P 1992), and Masny-Rindal OT, introduced by Masny and Rindal (ACM CCS 2019), are highly-efficient methods for compiling essentially any KEM into advanced…

Preprint: theory
Paper
arXiv

Rate 1/5 Non-Malleable Codes against Entangled Split-State Tampering

Naresh Goud Boddu

We construct efficient information-theoretic non-malleable codes for classical messages that are secure against two noncommunicating local quantum tampering operations…We construct efficient information-theoretic non-malleable codes for classical messages that are secure against two noncommunicating local quantum tampering operations with arbitrary pre-shared entanglement.

Preprint: theory
Paper
arXiv

Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

Robert Koenig, Marco Tomamichel

We consider quantum circuits consisting of d layers of nearest-neighbor two-qubit gates acting on n qubits arranged on a line, where every qubit is independently…We consider quantum circuits consisting of d layers of nearest-neighbor two-qubit gates acting on n qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer.

Preprint: theory
Paper
arXiv

Constant-Overhead Injection into Quantum Codes

Louis Golowich, Venkatesan Guruswami

We construct the first known fault-tolerant scheme for injecting states into quantum error-correcting codes with constant space and time overhead.We construct the first known fault-tolerant scheme for injecting states into quantum error-correcting codes with constant space and time overhead.

Preprint: theory
Paper
arXiv

Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

Prabhanjan Ananth, Yao-Ting Lin

A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time…A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is…

Preprint: theory
Paper
arXiv

Classical Algorithms for Function Computation in Gaussian Boson Sampling

Ruoting Dou, Hao Zhan, Shengjun Wu et al.

Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics.Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics.

Preprint: theory
Paper