Aram W. Harrow

Aram W. Harrow

Auto-generated profile, based on publicly available information

Aram W. Harrow

Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, USA

Research Focus & Metrics

Academic Career Length

25Years (2002-Present)

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

Representative Publications

View All Publications
3 August 2016 in Communications in Mathematical Physics
Verified
Journal Article
Open access
PDF file
FBFernando G. S. L. Brandão
Fernando G. S. L. Brandão
AHAram W. Harrow
Aram W. Harrow
MHMichał Horodecki
Michał Horodecki
We prove that local random quantum circuits acting on n qubits composed of O(t 10 n 2) many nearest neighbor two-qubit gates form an approximate unitary t-design. Previously it was unknown whether random quantum circuits were a t-design for any t > 3. The proof is based on an interplay of techniques from quantum many-body theory, representation theory, and the theory of Markov chains. In particular we employ a result of Nachtergaele for lower bounding the spectral gap of frustration-free quantum local Hamiltonians; a quasi-orthogonality property of permutation matrices; a result of Oliveira which extends to the unitary group the path-coupling method for bounding the mixing time of random walks; and a result of Bourgain and Gamburd showing that dense subgroups of the special unitary group, composed of elements with algebraic entries, are ∞-copy tensor-product expanders. We also consider pseudo-randomness properties of local random quantum circuits of small depth and prove that circuits of depth O(t 10 n) constitute a quantum t-copy tensor-product expander. The proof also rests on techniques from quantum many-body theory, in particular on the detectability lemma of Aharonov, Arad, Landau, and Vazirani. We give applications of the results to cryptography, equilibration of closed quantum dynamics, and the generation of topological order. In particular we show the following pseudo-randomness property of generic quantum circuits: Almost every circuit U of size O(n k) on n qubits cannot be distinguished from a Haar uniform unitary by circuits of size O(n (k-9)/11) that are given oracle access to U.

23 June 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
JHJeongwan Haah
Jeongwan Haah
AHAram W. Harrow
Aram W. Harrow
ZJZhengfeng Ji
Zhengfeng Ji
XWXiaodi Wu
Xiaodi Wu
NYNengkun Yu
Nengkun Yu
It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr 2 /ε 2 ) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε 2 )ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr 2 /δ 2 )/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.

11 July 2003 in Physical Review A
Verified
Journal Article
Closed access
PDF file
AHAram W. Harrow
Aram W. Harrow
MNMichael A. Nielsen
Michael A. Nielsen
We define several quantitative measures of the robustness of a quantum gate against noise. Exact analytic expressions for the robustness against depolarizing noise are obtained for all bipartite unitary quantum gates, and it is found that the controlled-NOT gate is the most robust two-qubit quantum gate, in the sense that it is the quantum gate which can tolerate the most depolarizing noise and still generate entanglement. Our results enable us to place several analytic upper bounds on the value of the threshold for quantum computation, with the best bound in the most pessimistic error model being pth<~0.5.

4 May 2023 in Communications in Mathematical Physics
Verified
Journal Article
Open access
PDF file
AHAram W. Harrow
Aram W. Harrow
SMSaeed Mehraban
Saeed Mehraban
We prove that $${{\,\textrm{poly}\,}}(t) \cdot n^{1/D}$$ poly ( t ) · n 1 / D -depth local random quantum circuits with two qudit nearest-neighbor gates on a D-dimensional lattice with n qudits are approximate t-designs in various measures. These include the “monomial” measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was $${{\,\textrm{poly}\,}}(t)\cdot n$$ poly ( t ) · n due to Brandão–Harrow–Horodecki (Commun Math Phys 346(2):397–434, 2016) for $$D=1$$ D = 1 . We also improve the “scrambling” and “decoupling” bounds for spatially local random circuits due to Brown and Fawzi (Scrambling speed of random quantum circuits, 2012). One consequence of our result is that assuming the polynomial hierarchy ( $${{\,\mathrm{\textsf{PH}}\,}}$$ PH ) is infinite and that certain counting problems are $$\#{\textsf{P}}$$ # P -hard “on average”, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constant-depth quantum circuits was known to be hard for classical computers under these assumptions. However the standard strategy for extending this hardness result to approximate sampling requires the quantum circuits to have a property called “anti-concentration”, meaning roughly that the output has near-maximal entropy. Unitary 2-designs have the desired anti-concentration property. Our result improves the required depth for this level of anti-concentration from linear depth to a sub-linear value, depending on the geometry of the interactions. This is relevant to a recent experiment by the Google Quantum AI group to perform such a sampling task with 53 qubits on a two-dimensional lattice (Arute in Nature 574(7779):505–510, 2019; Boixo et al. in Nate Phys 14(6):595–600, 2018) (and related experiments by USTC), and confirms their conjecture that $$O(\sqrt{n})$$ O ( n ) depth suffices for anti-concentration. The proof is based on a previous construction of t-designs by Brandão et al. (2016), an analysis of how approximate designs behave under composition, and an extension of the quasi-orthogonality of permutation operators developed by Brandão et al. (2016). Different versions of the approximate design condition correspond to different norms, and part of our contribution is to introduce the norm corresponding to anti-concentration and to establish equivalence between these various norms for low-depth circuits. For random circuits with long-range gates, we use different methods to show that anti-concentration happens at circuit size $$O(n\ln ^2 n)$$ O ( n ln 2 n ) corresponding to depth $$O(\ln ^3 n)$$ O ( ln 3 n ) . We also show a lower bound of $$\Omega (n \ln n)$$ Ω ( n ln n ) for the size of such circuit in this case. We also prove that anti-concentration is possible in depth $$O(\ln n \ln \ln n)$$ O ( ln n ln ln n ) (size $$O(n \ln n \ln \ln n)$$ O ( n ln n ln ln n ) ) using a different model.

7 April 2021 in Physical Review Letters
Verified
Journal Article
Closed access
PDF file
AHAram W. Harrow
Aram W. Harrow
JNJohn C. Napp
John C. Napp
Within a natural black-box setting, we exhibit a simple optimization problem for which a quantum variational algorithm that measures analytic gradients of the objective function with a low-depth circuit and performs stochastic gradient descent provably converges to an optimum faster than any algorithm that only measures the objective function itself, settling the question of whether measuring analytic gradients in such algorithms can ever be beneficial. We also derive upper bounds on the cost of gradient-based variational optimization near a local minimum.

3 December 2004 in Physical Review Letters
Verified
Journal Article
Closed access
PDF file
IDIgor Devetak
Igor Devetak
AHAram W. Harrow
Aram W. Harrow
AWAndreas Winter
Andreas Winter
We introduce three new quantum protocols involving noisy quantum channels and entangled states, and relate them operationally and conceptually with four well-known old protocols. Two of the new protocols (the mother and father) can generate the other five “child” protocols by direct application of teleportation and superdense coding, and can be derived in turn by making the old protocols “coherent.” This gives very simple proofs for two famous old protocols (the hashing inequality and quantum channel capacity) and provides the basis for optimal trade-off curves in several quantum information processing tasks.