Boaz Barak

Boaz Barak

Auto-generated profile, based on publicly available information

Boaz Barak

Harvard University

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
10 June 2022 in Science
Verified
Journal Article
Closed access
SES. Ebadi
S. Ebadi
AKA. Keesling
A. Keesling
MCM. Cain
M. Cain
TWT. T. Wang
T. T. Wang
HLH. Levine
H. Levine
MLM. D. Lukin
M. D. Lukin
Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm’s performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.

29 February 2024 in PRX Quantum
Verified
Journal Article
Open access
PDF file
XGXun Gao
Xun Gao
MKMarcin Kalinowski
Marcin Kalinowski
CCChi-Ning Chou
Chi-Ning Chou
MLMikhail D. Lukin
Mikhail D. Lukin
BBBoaz Barak
Boaz Barak
SCSoonwon Choi
Soonwon Choi
Demonstrating quantum advantage requires experimental implementation of a computational task that is hard to achieve using state-of-the-art classical systems. One approach is to perform sampling from a probability distribution associated with a certain class of highly entangled many-body wave functions. It has been suggested that such a quantum advantage can be certified with the linear cross-entropy benchmark (XEB). We critically examine this notion. First, we consider a “benign” setting, where an honest implementation of a noisy quantum circuit is assumed, and characterize the conditions under which the XEB approximates the fidelity of quantum dynamics. Second, we assume an “adversarial” setting, where all possible classical algorithms are considered for comparisons, and show that achieving relatively high XEB values does not imply faithful simulation of quantum dynamics. Specifically, we present an efficient classical algorithm that achieves high XEB values, namely 5–12% of those obtained in the state-of-the-art experiments, within just a few seconds using a single GPU machine. This is made possible by identifying and exploiting several vulnerabilities of the XEB, which allows us to achieve high XEB values without simulating a full quantum circuit. Remarkably, our algorithm features better scaling with the system size than a noisy quantum device for commonly studied random circuit ensembles in various architecture. We quantitatively explain the success of our algorithm and the limitations of the XEB by using a theoretical framework, in which the dynamics of the average XEB and fidelity are mapped to classical statistical mechanics models. Using this framework, we illustrate the relation between the XEB and the fidelity for quantum circuits in various architectures, with different choices of gate sets, and in the presence of noise. Taken together, our results demonstrate that XEB’s utility as a proxy for fidelity hinges on several conditions, which should be independently checked in the benign setting, but cannot be assumed in the general adversarial setting. Therefore, the XEB on its own has a limited utility as a benchmark for quantum advantage. We briefly discuss potential ways to overcome these limitations.

31 March 2018
Verified
Book Chapter
Closed access
PDF file
BBBoaz Barak
Boaz Barak
ZBZvika Brakerski
Zvika Brakerski
IKIlan Komargodski
Ilan Komargodski
PKPravesh K. Kothari
Pravesh K. Kothari

6 April 2017
Verified
Book Chapter
Closed access
PDF file
BBBoaz Barak
Boaz Barak

18 April 2019
Verified
Book Chapter
Closed access
PDF file
BBBoaz Barak
Boaz Barak
SHSamuel B. Hopkins
Samuel B. Hopkins
AJAayush Jain
Aayush Jain
PKPravesh Kothari
Pravesh Kothari
ASAmit Sahai
Amit Sahai

29 March 2022 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
BBBoaz Barak
Boaz Barak
AMAnkur Moitra
Ankur Moitra
In the noisy tensor completion problem we observementries (whose location is chosen uniformly at random) from an unknown $$n_1 \times n_2 \times n_3$$n1×n2×n3 tensorT. We assume thatTis entry-wise close to being rankr. Our goal is to fill in its missing entries using as few observations as possible. Let $$n = \max (n_1, n_2, n_3)$$n=max(n1,n2,n3) . We show that if $$m > rsim n^{3/2} r$$m≳n3/2r then there is a polynomial time algorithm based on the sixth level of the sum-of-squares hierarchy for completing it. Our estimate agrees with almost all ofT’s entries almost exactly and works even when our observations are corrupted by noise. This is also the first algorithm for tensor completion that works in the overcomplete case when $$r > n$$r>n , and in fact it works all the way up to $$r = n^{3/2-\epsilon }$$r=n3/2-ϵ . Our proofs are short and simple and are based on establishing a new connection between noisy tensor completion (through the language of Rademacher complexity) and the task of refuting random constraint satisfaction problems. This connection seems to have gone unnoticed even in the context of matrix completion. Furthermore, we use this connection to show matching lower bounds. Our main technical result is in characterizing the Rademacher complexity of the sequence of norms that arise in the sum-of-squares relaxations to the tensor nuclear norm. These results point to an interesting new direction: Can we explore computational vs. sample complexity tradeoffs through the sum-of-squares hierarchy?