BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Zeph Landau

Zeph Landau appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phcond-mat.str-elComputational Complexitymath.COmath.PRcond-mat.othermath.DSmath.GR

Catalog footprint

What is connected

13works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2022arXiv

Distributed quantum inner product estimation

As small quantum computers are becoming available on different physical platforms, a benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. This task is fundamentally distributed, as no quantum communication can be performed between the two physical platforms due to hardware constraints, which prohibits a joint SWAP test. In this paper we settle the sample complexity of this task across all measurement and communication settings. The essence of the task, which we call distributed quantum inner product estimation, involves two players Alice and Bob who have $k$ copies of unknown states $ρ,σ$ (acting on $\mathbb{C}^{d}$) respectively. Their goal is to estimate $\mathrm{Tr}(ρσ)$ up to additive error $\varepsilon\in(0,1)$, using local quantum operations and classical communication. In the weakest setting where only non-adaptive single-copy measurements and simultaneous message passing are allowed, we show that $k=O(\max\{1/\varepsilon^2,\sqrt{d}/\varepsilon\})$ copies suffice. This achieves a savings compared to full tomography which takes $Ω(d^3)$ copies with single-copy measurements. Surprisingly, we also show that the sample complexity must be at least $Ω(\max\{1/\varepsilon^2,\sqrt{d}/\varepsilon\})$, even in the strongest setting where adaptive multi-copy measurements and arbitrary rounds of communication are allowed. This shows that the success achieved by shadow tomography, for sample-efficiently learning the properties of a single system, cannot be generalized to the distributed setting. Furthermore, the fact that the sample complexity remains the same with single and multi-copy measurements contrasts with single system quantum property testing, which often demonstrate exponential separations in sample complexity with single and multi-copy measurements.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Noise and the frontier of quantum supremacy

Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step forward, but gaps remain between the theory behind these experiments and their actual implementations. In this work we initiate the study of the complexity of quantum random circuit sampling experiments with realistic amounts of noise. Actual quantum supremacy experiments have high levels of uncorrected noise and exponentially decaying fidelities. It is natural to ask if there is any signal of exponential complexity in these highly noisy devices. Surprisingly, we show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction. More formally, so long as the noise rate of the device is below the error detection threshold, we show it is #P-hard to compute the output probabilities of random circuits with a constant rate of noise per gate. This hardness persists even though these probabilities are exponentially close to uniform. Interestingly these hardness results also have implications for the complexity of experiments in a low-noise setting. The issue here is that prior hardness results for computing output probabilities of random circuits are not robust enough to imprecision to connect with the Stockmeyer argument for hardness of sampling from circuits with constant fidelity. We exponentially improve the robustness of prior results to imprecision, both in the cases of Random Circuit Sampling and BosonSampling. In the latter case we bring the proven hardness within a constant factor in the exponent of the robustness required for hardness of sampling for the first time. We then show that our results are in tension with one another -- the high-noise result implies the low-noise result is essentially optimal, even with generalizations of our techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Germ order for one-dimensional packings

Every set of natural numbers determines a generating function convergent for $q \in (-1,1)$ whose behavior as $q \rightarrow 1^-$ determines a germ. These germs admit a natural partial ordering that can be used to compare sets of natural numbers in a manner that generalizes both cardinality of finite sets and density of infinite sets. For any finite set $D$ of positive integers, call a set $S$ "$D$-avoiding" if no two elements of $S$ differ by an element of $D$. We study the problem of determining, for fixed $D$, all $D$-avoiding sets that are maximal in the germ order. In many cases, we can show that there is exactly one such set. We apply this to the study of one-dimensional packing problems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Dull cut off for circulants

Families of symmetric simple random walks on Cayley graphs of Abelian groups with a bound on the number of generators are shown to never have sharp cut off in the sense of [1], [3], or [5]. Here convergence to the stationary distribution is measured in the total variation norm. This is a situation of bounded degree and no expansion. Sharp cut off or the cut off phenomenon has been shown to occur in families such as random walks on a hypercube [1] in which the degree is unbounded as well as on a random regular graph where the degree is fixed, but there is expansion [4]. Our examples agree with Peres' conjecture in [3] relating sharp cut off, spectral gap, and mixing time.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Quantum Hamiltonian Complexity

Constraint satisfaction problems are a central pillar of modern computational complexity theory. This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint satisfaction problems. Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a "Quantum Cook-Levin Theorem" to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws. Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field. As such, we include the following in this survey: (1) The motivations and history of the field, (2) a glossary of condensed matter physics terms explained in computer-science friendly language, (3) overviews of central ideas from condensed matter physics, such as indistinguishable particles, mean field theory, tensor networks, and area laws, and (4) brief expositions of selected computer science-based results in the area. For example, as part of the latter, we provide a novel information theoretic presentation of Bravyi's polynomial time algorithm for Quantum 2-SAT.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Sums of twisted circulants

The rate of convergence of simple random walk on the Heisenberg group over $Z/nZ$ with a standard generating set was determined by Bump et al [1,2]. We extend this result to random walks on the same groups with an arbitrary minimal symmetric generating set. We also determine the rate of convergence of simple random walk on higher-dimensional versions of the Heisenberg group with a standard generating set. We obtain our results via Fourier analysis, using an eigenvalue bound for sums of twisted circulant matrices. The key tool is a generalization of a version of the Heisenberg Uncertainty Principle due to Donoho-Stark [4].

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Connecting global and local energy distributions in quantum spin models on a lattice

Generally, the local interactions in a many-body quantum spin system on a lattice do not commute with each other. Consequently, the Hamiltonian of a local region will generally not commute with that of the entire system, and so the two cannot be measured simultaneously. The connection between the probability distributions of measurement outcomes of the local and global Hamiltonians will depend on the angles between the diagonalizing bases of these two Hamiltonians. In this paper we characterize the relation between these two distributions. On one hand, we upperbound the probability of measuring an energy $τ$ in a local region, if the global system is in a superposition of eigenstates with energies $ε<τ$. On the other hand, we bound the probability of measuring a global energy $ε$ in a bipartite system that is in a tensor product of eigenstates of its two subsystems. Very roughly, we show that due to the local nature of the governing interactions, these distributions are identical to what one encounters in the commuting case, up to some exponentially small corrections. Finally, we use these bounds to study the spectrum of a locally truncated Hamiltonian, in which the energies of a contiguous region have been truncated above some threshold energy $τ$. We show that the lower part of the spectrum of this Hamiltonian is exponentially close to that of the original Hamiltonian. A restricted version of this result in 1D was a central building block in a recent improvement of the 1D area-law.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Local tests of global entanglement and a counterexample to the generalized area law

We introduce a technique for applying quantum expanders in a distributed fashion, and use it to solve two basic questions: testing whether a bipartite quantum state shared by two parties is the maximally entangled state and disproving a generalized area law. In the process these two questions which appear completely unrelated turn out to be two sides of the same coin. Strikingly in both cases a constant amount of resources are used to verify a global property.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians

Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An area law and sub-exponential algorithm for 1D systems

We give a new proof for the area law for general 1D gapped systems, which exponentially improves Hastings' famous result \cite{ref:Has07}. Specifically, we show that for a chain of d-dimensional spins, governed by a 1D local Hamiltonian with a spectral gap \eps>0, the entanglement entropy of the ground state with respect to any cut in the chain is upper bounded by $O{\frac{\log^3 d}{\eps}}$. Our approach uses the framework Arad et al to construct a Chebyshev-based AGSP (Approximate Ground Space Projection) with favorable factors. However, our construction uses the Hamiltonian directly, instead of using the Detectability lemma, which allows us to work with general (frustrated) Hamiltonians, as well as slightly improving the $1/\eps$ dependence of the bound in Arad et al. To achieve that, we establish a new, "random-walk like", bound on the entanglement rank of an arbitrary power of a 1D Hamiltonian, which might be of independent interest: \ER{H^\ell} \le (\ell d)^{O(\sqrt{\ell})}. Finally, treating d as a constant, our AGSP shows that the ground state is well approximated by a matrix product state with a sublinear bond dimension $B=e^{O(\log^{3/4}n/\eps^{1/4})}. Using this in conjunction with known dynamical programing algorithms, yields an algorithm for a 1/\poly(n) approximation of the ground energy with a subexponential running time T\le \exp(e^{O(\log^{3/4}n/\eps^{1/4})}).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quantum Hamiltonian complexity and the detectability lemma

Quantum Hamiltonian complexity studies computational complexity aspects of local Hamiltonians and ground states; these questions can be viewed as generalizations of classical computational complexity problems related to local constraint satisfaction (such as SAT), with the additional ingredient of multi-particle entanglement. This additional ingredient of course makes generalizations of celebrated theorems such as the PCP theorem from classical to the quantum domain highly non-trivial; it also raises entirely new questions such as bounds on entanglement and correlations in ground states, and in particular area laws. We propose a simple combinatorial tool that helps to handle such questions: it is a simplified, yet more general version of the detectability lemma introduced by us in the more restricted context on quantum gap amplification a year ago. Here, we argue that this lemma is applicable in much more general contexts. We use it to provide a simplified and more combinatorial proof of Hastings' 1D area law, together with a less than 1 page proof of the decay of correlations in gapped local Hamiltonian systems in any constant dimension. We explain how the detectability lemma can replace the Lieb-Robinson bound in various other contexts, and argue that it constitutes a basic tool for the study of local Hamiltonians and their ground states in relation to various questions in quantum Hamiltonian complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Distributions of order patterns of interval maps

A permutation $σ$ describing the relative orders of the first $n$ iterates of a point $x$ under a self-map $f$ of the interval $I=[0,1]$ is called an \emph{order pattern}. For fixed $f$ and $n$, measuring the points $x\in I$ (according to Lebesgue measure) that generate the order pattern $σ$ gives a probability distribution $μ_n(f)$ on the set of length $n$ permutations. We study the distributions that arise this way for various classes of functions $f$. Our main results treat the class of measure preserving functions. We obtain an exact description of the set of realizable distributions in this case: for each $n$ this set is a union of open faces of the polytope of flows on a certain digraph, and a simple combinatorial criterion determines which faces are included. We also show that for general $f$, apart from an obvious compatibility condition, there is no restriction on the sequence $\{μ_n(f)\}$ for $n=1,2,...$. In addition, we give a necessary condition for $f$ to have \emph{finite exclusion type}, i.e., for there to be finitely many order patterns that generate all order patterns not realized by $f$. Using entropy we show that if $f$ is piecewise continuous, piecewise monotone, and either ergodic or with points of arbitrarily high period, then $f$ cannot have finite exclusion type. This generalizes results of S. Elizalde.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Quantum computation and the evaluation of tensor networks

We present a quantum algorithm that additively approximates the value of a tensor network to a certain scale. When combined with existing results, this provides a complete problem for quantum computation. The result is a simple new way of looking at quantum computation in which unitary gates are replaced by tensors and time is replaced by the order in which the tensor-network is "swallowed". We use this result to derive new quantum algorithms that approximate the partition function of a variety of classical statistical mechanics models, including the Potts model.

0 citations0 reviewsNo code linkedOpen access