41 citations · 54 across the 19 of their papers we have counts for
27 papers
Error Mitigation From a Single Unmodified Error-Corrected Circuit
Maor Shutman, Dorit Aharonov, Itai Arad +7
Recent work has shown that syndrome information obtained during error-corrected quantum computation can be utilized for logical error mitigation (LEM), yielding exponential reducti…
Tight Post-Quantum Parallel Repetition for Private-Coin Arguments
Zvika Brakerski, Andrew Huang, Yael Tauman Kalai +1
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness…
Generic Number-of-Copies Amplification for Pseudorandom States
Zvika Brakerski, Miri Zenilman
We show that any quantum pseudorandom state that is secure against single-copy distinguishers, i.e. a -PRS, can be amplified to -copy security, i.e. to a -PRS, without add…
On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem
Zvika Brakerski, Henry Yuen
We consider the task of constructing pseudorandom unitaries (PRUs) with scalable security, i.e. families in which the security parameter may vary independently of the dimension (or…
Syndrome aware mitigation of logical errors
Dorit Aharonov, Yosi Atia, Eyal Bairey +6
Broad applications of quantum computers will require error correction (EC). However, hardware roadmaps indicate that physical qubit numbers will remain limited in the foreseeable f…
Reliable high-accuracy error mitigation for utility-scale quantum circuits
Dorit Aharonov, Ori Alberton, Itai Arad +36
Error mitigation is essential for unlocking the full potential of quantum algorithms and accelerating the timeline toward quantum advantage. As quantum hardware progresses to push…
State-Based Classical Shadows
Zvika Brakerski, Nir Magrafta, Tomer Solomon
Classical Shadow Tomography (Huang, Kueng and Preskill, Nature Physics 2020) is a method for creating a classical snapshot of an unknown quantum state, which can later be used to p…
On the Importance of Error Mitigation for Quantum Computation
Dorit Aharonov, Ori Alberton, Itai Arad +13
Quantum error mitigation (EM) is a family of hybrid quantum-classical methods for eliminating or reducing the effect of noise and decoherence on quantum algorithms run on quantum h…
Real-Valued Somewhat-Pseudorandom Unitaries
Zvika Brakerski, Nir Magrafta
We explore a very simple distribution of unitaries: random (binary) phase -- Hadamard -- random (binary) phase -- random computational-basis permutation. We show that this distribu…
Quantum State Obfuscation from Classical Oracles
James Bartusek, Zvika Brakerski, Vinod Vaikuntanathan
A major unresolved question in quantum cryptography is whether it is possible to obfuscate arbitrary quantum computation. Indeed, there is much yet to understand about the feasibil…
Computational Entanglement Theory
Rotem Arnon, Zvika Brakerski, Thomas Vidick
We initiate a rigorous study of computational entanglement theory, inspired by the emerging usefulness of ideas from quantum information theory in computational complexity. We defi…
Simple Tests of Quantumness Also Certify Qubits
Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer +2
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain templ…
Lattice Problems Beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, Zvika Brakerski +6
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-…
Black-Hole Radiation Decoding is Quantum Cryptography
Zvika Brakerski
We propose to study equivalence relations between phenomena in high-energy physics and the existence of standard cryptographic primitives, and show the first example where such an…
On the computational hardness needed for quantum cryptography
Zvika Brakerski, Ran Canetti, Luowen Qian
In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptograph…
Constructive Post-Quantum Reductions
Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai
Is it possible to convert classical cryptographic reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interac…
Unitary Subgroup Testing
Zvika Brakerski, Devika Sharma, Guy Weissenberg
We consider the problem of for a quantum circuit : given access to , determine whether it implements a unitary that is -close or -far from a…
On the Hardness of Average-case k-SUM
Zvika Brakerski, Noah Stephens-Davidowitz, Vinod Vaikuntanathan
In this work, we show the first worst-case to average-case reduction for the classical -SUM problem. A -SUM instance is a collection of integers, and the goal of the -…
Quantum Garbled Circuits
Zvika Brakerski, Henry Yuen
We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encodin…
Simpler Proofs of Quantumness
Zvika Brakerski, Venkata Koppula, Umesh Vazirani +1
A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparabl…
Impossibility of Quantum Virtual Black-Box Obfuscation of Classical Circuits
Gorjan Alagic, Zvika Brakerski, Yfke Dulek +1
Virtual black-box obfuscation is a strong cryptographic primitive: it encrypts a circuit while maintaining its full input/output functionality. A remarkable result by Barak et al.…
Scalable Pseudorandom Quantum States
Zvika Brakerski, Omri Shmueli
Efficiently sampling a quantum state that is hard to distinguish from a truly random quantum state is an elementary task in quantum information theory that has both computational a…
(Pseudo) Random Quantum States with Binary Phase
Zvika Brakerski, Omri Shmueli
We prove a quantum information-theoretic conjecture due to Ji, Liu and Song (CRYPTO 2018) which suggested that a uniform superposition with random \emph{binary} phase is statistica…
On Quantum Advantage in Information Theoretic Single-Server PIR
Dorit Aharonov, Zvika Brakerski, Kai-Min Chung +3
In (single-server) Private Information Retrieval (PIR), a server holds a large database of size , and a client holds an index and wishes to retrieve wit…