Approaching the Quantum Singleton Bound with Approximate Error Correction

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=ZuZuVu9igTU


Duration: 1:32:56
1,085 views
19

Sam Gunn (UC Berkeley)
https://simons.berkeley.edu/events/quantum-colloquium-approaching-quantum-singleton-bound-approximate-error-correction
Quantum Colloquium

It is well known that no quantum error correcting code of rate R can correct adversarial errors on more than a (1-R)/4 fraction of symbols. But what if we only require our codes to *approximately* recover the message?

In this work, we construct efficiently-decodable approximate quantum codes against adversarial error rates approaching the quantum singleton bound of (1-R)/2, for any constant rate R. Moreover, the size of the alphabet is a constant independent of the message length and the recovery error is exponentially small in the message length.

Central to our construction is a notion of quantum list decoding and an implementation involving folded quantum Reed-Solomon codes.

Joint work with Thiago Bergamaschi (UC Berkeley) and Louis Golowich (UC Berkeley).

Panel featuring Steve Flammia (AWS), Venkat Guruswami (UC Berkeley), and Debbie Leung (University of Waterloo); Umesh Vazirani (UC Berkeley; moderator).



Other Videos By Simons Institute for the Theory of Computing


2023-01-03Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
2023-01-03Loss Minimization through the lens of Outcome Indistinguishability
2022-12-27PACE Tech: Physics and Algorithms Coupled to Enhance Technology
2022-12-13NLTS Hamiltonians from Codes — Panel | Quantum Colloquium
2022-12-13Panel Discussion
2022-12-13'How to “Multiply” Quantum States'
2022-12-13"The Problem with Qubits"
2022-12-13"Fault Tolerance with Biased Noise Qubits: Challenges and Opportunities"
2022-12-13"Complexity and Applications of Random Circuit Sampling"
2022-12-13"Analog and Digital Quantum Computing with Neutral Atoms"
2022-12-07Approaching the Quantum Singleton Bound with Approximate Error Correction
2022-12-02Aggregative Efficiency of Bayesian Learning in Networks
2022-12-02(Relaxing) Common Belief for Social Networks
2022-12-02Organizing Modular Production
2022-12-02Social Learning and Sample Herding in Networks with Homophily
2022-12-02Experimentation on Networks
2022-12-01Too Much Data: Externalities and Inefficiencies in Data Markets
2022-12-01Experimental and Observational Studies in the Presence of Stochastic Networks
2022-12-01Learning in Repeated Interactions on Networks
2022-12-01Persuasion in Networks: Public Signals and Cores
2022-12-01Market Power and Tax Interventions: A Principal Components Approach


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Quantum Colloquium
Sam Gunn
Steve Flammia
Venkat Guruswami
Debbie Leung
Umesh Vazirani