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

David Gross

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

ResearcherUnclaimed source record
quant-phInformation Theorymath-phmath.ITmath.MPMachine Learningcond-mat.stat-mechhep-phhep-thmath.NAmath.OCmath.PRmath.STNumerical Analysisphysics.chem-phStatistics Theory

Catalog footprint

What is connected

30works
16topics
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

30 published item(s)

preprint2021arXiv

Stabilizer extent is not multiplicative

The Gottesman-Knill theorem states that a Clifford circuit acting on stabilizer states can be simulated efficiently on a classical computer. Recently, this result has been generalized to cover inputs that are close to a coherent superposition of logarithmically many stabilizer states. The runtime of the classical simulation is governed by the stabilizer extent, which roughly measures how many stabilizer states are needed to approximate the state. An important open problem is to decide whether the extent is multiplicative under tensor products. An affirmative answer would yield an efficient algorithm for computing the extent of product inputs, while a negative result implies the existence of more efficient classical algorithms for simulating largescale quantum circuits. Here, we answer this question in the negative. Our result follows from very general properties of the set of stabilizer states, such as having a size that scales subexponentially in the dimension, and can thus be readily adapted to similar constructions for other resource theories.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

From estimation of quantum probabilities to simulation of quantum circuits

Investigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depends quite critically on the precise notion of "classical simulation" and in particular on the required accuracy. We argue that a notion of classical simulation, which we call epsilon-simulation, captures the essence of possessing "equivalent computational power" as the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an epsilon-simulator from one possessing the simulated quantum system. We relate epsilon-simulation to various alternative notions of simulation predominantly focusing on a simulator we call a poly-box. A poly-box outputs 1/poly precision additive estimates of Born probabilities and marginals. This notion of simulation has gained prominence through a number of recent simulability results. Accepting some plausible computational theoretic assumptions, we show that epsilon-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to epsilon-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution (poly-sparsity).

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Implications of pinned occupation numbers for natural orbital expansions. II: Rigorous derivation and extension to non-fermionic systems

We have explained and comprehensively illustrated in Part I that the generalized Pauli constraints suggest a natural extension of the concept of active spaces. In the present Part II, we provide rigorous derivations of the theorems involved therein. This will offer in particular deeper insights into the underlying mathematical structure and will explain why the saturation of generalized Pauli constraints implies a specific simplified structure of the corresponding many-fermion quantum state. Moreover, we extend the results of Part I to non-fermionic multipartite quantum systems, revealing that extremal single-body information has always strong implications for the multipartite quantum state. In that sense, our work also confirms that pinned quantum systems define new physical entities and the presence of pinnings reflect the existence of (possibly hidden) ground state symmetries.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Semidefinite tests for latent causal structures

Testing whether a probability distribution is compatible with a given Bayesian network is a fundamental task in the field of causal inference, where Bayesian networks model causal relations. Here we consider the class of causal structures where all correlations between observed quantities are solely due to the influence from latent variables. We show that each model of this type imposes a certain signature on the observable covariance matrix in terms of a particular decomposition into positive semidefinite components. This signature, and thus the underlying hypothetical latent structure, can be tested in a computationally efficient manner via semidefinite programming. This stands in stark contrast with the algebraic geometric tools required if the full observable probability distribution is taken into account. The semidefinite test is compared with tests based on entropic inequalities.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distinguishing quantum states using Clifford orbits

It is a fundamental property of quantum mechanics that information is lost as a result of performing measurements. Indeed, with every quantum measurement one can associate a number -- its POVM norm constant -- that quantifies how much the distinguishability of quantum states degrades in the worst case as a result of the measurement. This raises the obvious question which measurements preserve the most information in these sense of having the largest norm constant. While a number of near-optimal schemes have been found (e.g. the uniform POVM, or complex projective 4-designs), they all seem to be difficult to implement in practice. Here, we analyze the distinguishability of quantum states under measurements that are orbits of the Clifford group. The Clifford group plays an important role e.g. in quantum error correction, and its elements are considered simple to implement. We find that the POVM norm constants of Clifford orbits depend on the effective rank of the states that should be distinguished, as well as on a quantitative measure of the "degree of localization in phase space" of the vectors in the orbit. The most important Clifford orbit is formed by the set of stabilizer states. Our main result implies that stabilizer measurements are essentially optimal for distinguishing pure quantum states. As an auxiliary result, we use the methods developed here to prove new entropic uncertainty relations for stabilizer measurements. This paper is based on a very recent analysis of the representation theory of tensor powers of the Clifford group.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Low rank matrix recovery from Clifford orbits

We prove that low-rank matrices can be recovered efficiently from a small number of measurements that are sampled from orbits of a certain matrix group. As a special case, our theory makes statements about the phase retrieval problem. Here, the task is to recover a vector given only the amplitudes of its inner product with a small number of vectors from an orbit. Variants of the group in question have appeared under different names in many areas of mathematics. In coding theory and quantum information, it is the complex Clifford group; in time-frequency analysis the oscillator group; and in mathematical physics the metaplectic group. It affords one particularly small and highly structured orbit that includes and generalizes the discrete Fourier basis: While the Fourier vectors have coefficients of constant modulus and phases that depend linearly on their index, the vectors in said orbit have phases with a quadratic dependence. In quantum information, the orbit is used extensively and is known as the set of stabilizer states. We argue that due to their rich geometric structure and their near-optimal recovery properties, stabilizer states form an ideal model for structured measurements for phase retrieval. Our results hold for $m\geq C κ_r r d \log(d)$ measurements, where the oversampling factor k varies between $κ_r=1$ and $κ_r = r^2$ depending on the orbit. The reconstruction is stable towards both additive noise and deviations from the assumption of low rank. If the matrices of interest are in addition positive semidefinite, reconstruction may be performed by a simple constrained least squares regression. Our proof methods could be adapted to cover orbits of other groups.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Clifford group fails gracefully to be a unitary 4-design

A unitary t-design is a set of unitaries that is "evenly distributed" in the sense that the average of any t-th order polynomial over the design equals the average over the entire unitary group. In various fields -- e.g. quantum information theory -- one frequently encounters constructions that rely on matrices drawn uniformly at random from the unitary group. Often, it suffices to sample these matrices from a unitary t-design, for sufficiently high t. This results in more explicit, derandomized constructions. The most prominent unitary t-design considered in quantum information is the multi-qubit Clifford group. It is known to be a unitary 3-design, but, unfortunately, not a 4-design. Here, we give a simple, explicit characterization of the way in which the Clifford group fails to constitute a 4-design. Our results show that for various applications in quantum information theory and in the theory of convex signal recovery, Clifford orbits perform almost as well as those of true 4-designs. Technically, it turns out that in a precise sense, the 4th tensor power of the Clifford group affords only one more invariant subspace than the 4th tensor power of the unitary group. That additional subspace is a stabilizer code -- a structure extensively studied in the field of quantum error correction codes. The action of the Clifford group on this stabilizer code can be decomposed explicitly into previously known irreps of the discrete symplectic group. We give various constructions of exact complex projective 4-designs or approximate 4-designs of arbitrarily high precision from Clifford orbits. Building on results from coding theory, we give strong evidence suggesting that these orbits actually constitute complex projective 5-designs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Qubit stabilizer states are complex projective 3-designs

A complex projective $t$-design is a configuration of vectors which is ``evenly distributed'' on a sphere in the sense that sampling uniformly from it reproduces the moments of Haar measure up to order $2t$. We show that the set of all $n$-qubit stabilizer states forms a complex projective $3$-design in dimension $2^n$. Stabilizer states had previously only been known to constitute $2$-designs. The main technical ingredient is a general recursion formula for the so-called frame potential of stabilizer states. To establish it, we need to compute the number of stabilizer states with pre-described inner product with respect to a reference state. This, in turn, reduces to a counting problem in discrete symplectic vector spaces for which we find a simple formula. We sketch applications in quantum information and signal analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A unifying framework for relaxations of the causal assumptions in Bell's theorem

Bell's Theorem shows that quantum mechanical correlations can violate the constraints that the causal structure of certain experiments impose on any classical explanation. It is thus natural to ask to which degree the causal assumptions -- e.g. locality or measurement independence -- have to be relaxed in order to allow for a classical description of such experiments. Here, we develop a conceptual and computational framework for treating this problem. We employ the language of Bayesian networks to systematically construct alternative causal structures and bound the degree of relaxation using quantitative measures that originate from the mathematical theory of causality. The main technical insight is that the resulting problems can often be expressed as computationally tractable linear programs. We demonstrate the versatility of the framework by applying it to a variety of scenarios, ranging from relaxations of the measurement independence, locality and bilocality assumptions, to a novel causal interpretation of CHSH inequality violations.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Entanglement Polytopes: Multiparticle Entanglement from Single-Particle Information

Entangled many-body states are an essential resource for quantum computing and interferometry. Determining the type of entanglement present in a system usually requires access to an exponential number of parameters. We show that in the case of pure multi-particle quantum states, features of the global entanglement can already be extracted from local information alone. This is achieved by associating with any given class of entanglement an entanglement polytope---a geometric object which characterizes the single-particle states compatible with that class. Our results, applicable to systems of arbitrary size and statistics, give rise to local witnesses for global pure-state entanglement, and can be generalized to states affected by low levels of noise.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Experimental Comparison of Efficient Tomography Schemes for a Six-Qubit State

Quantum state tomography suffers from the measurement effort increasing exponentially with the number of qubits. Here, we demonstrate permutationally invariant tomography for which, contrary to conventional tomography, all resources scale polynomially with the number of qubits both in terms of the measurement effort as well as the computational power needed to process and store the recorded data. We demonstrate the benefits of combining permutationally invariant tomography with compressed sensing by studying the influence of the pump power on the noise present in a six-qubit symmetric Dicke state, a case where full tomography is possible only for very high pump powers.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Information-Theoretic Implications of Quantum Causal Structures

The correlations that can be observed between a set of variables depend on the causal structure underpinning them. Causal structures can be modeled using directed acyclic graphs, where nodes represent variables and edges denote functional dependencies. In this work, we describe a general algorithm for computing information-theoretic constraints on the correlations that can arise from a given interaction pattern, where we allow for classical as well as quantum variables. We apply the general technique to two relevant cases: First, we show that the principle of information causality appears naturally in our framework and go on to generalize and strengthen it. Second, we derive bounds on the correlations that can occur in a networked architecture, where a set of few-body quantum systems is distributed among a larger number of parties.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Causal structures from entropic information: Geometry and novel scenarios

The fields of quantum non-locality in physics, and causal discovery in machine learning, both face the problem of deciding whether observed data is compatible with a presumed causal relationship between the variables (for example a local hidden variable model). Traditionally, Bell inequalities have been used to describe the restrictions imposed by causal structures on marginal distributions. However, some structures give rise to non-convex constraints on the accessible data, and it has recently been noted that linear inequalities on the observable entropies capture these situations more naturally. In this paper, we show the versatility of the entropic approach by greatly expanding the set of scenarios for which entropic constraints are known. For the first time, we treat Bell scenarios involving multiple parties and multiple observables per party. Going beyond the usual Bell setup, we exhibit inequalities for scenarios with extra conditional independence assumptions, as well as a limited amount of shared randomness between the parties. Many of our results are based on a geometric observation: Bell polytopes for two-outcome measurements can be naturally imbedded into the convex cone of attainable marginal entropies. Thus, any entropic inequality can be translated into one valid for probabilities. In some situations the converse also holds, which provides us with a rich source of candidate entropic inequalities.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

RIPless compressed sensing from anisotropic measurements

Compressed sensing is the art of reconstructing a sparse vector from its inner products with respect to a small set of randomly chosen measurement vectors. It is usually assumed that the ensemble of measurement vectors is in isotropic position in the sense that the associated covariance matrix is proportional to the identity matrix. In this paper, we establish bounds on the number of required measurements in the anisotropic case, where the ensemble of measurement vectors possesses a non-trivial covariance matrix. Essentially, we find that the required sampling rate grows proportionally to the condition number of the covariance matrix. In contrast to other recent contributions to this problem, our arguments do not rely on any restricted isometry properties (RIP's), but rather on ideas from convex geometry which have been systematically studied in the theory of low-rank matrix recovery. This allows for a simple argument and slightly improved bounds, but may lead to a worse dependency on noise (which we do not consider in the present paper).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Scalable reconstruction of density matrices

Recent contributions in the field of quantum state tomography have shown that, despite the exponential growth of Hilbert space with the number of subsystems, tomography of one-dimensional quantum systems may still be performed efficiently by tailored reconstruction schemes. Here, we discuss a scalable method to reconstruct mixed states that are well approximated by matrix product operators. The reconstruction scheme only requires local information about the state, giving rise to a reconstruction technique that is scalable in the system size. It is based on a constructive proof that generic matrix product operators are fully determined by their local reductions. We discuss applications of this scheme for simulated data and experimental data obtained in an ion trap experiment.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Stabilizer information inequalities from phase space distributions

The Shannon entropy of a collection of random variables is subject to a number of constraints, the best-known examples being monotonicity and strong subadditivity. It remains an open question to decide which of these "laws of information theory" are also respected by the von Neumann entropy of many-body quantum states. In this article, we consider a toy version of this difficult problem by analyzing the von Neumann entropy of stabilizer states. We find that the von Neumann entropy of stabilizer states satisfies all balanced information inequalities that hold in the classical case. Our argument is built on the fact that stabilizer states have a classical model, provided by the discrete Wigner function: The phase-space entropy of the Wigner function corresponds directly to the von Neumann entropy of the state, which allows us to reduce to the classical case. Our result has a natural counterpart for multi-mode Gaussian states, which sheds some light on the general properties of the construction. We also discuss the relation of our results to recent work by Linden, Ruskai, and Winter.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Continuous-variable quantum compressed sensing

We significantly extend recently developed methods to faithfully reconstruct unknown quantum states that are approximately low-rank, using only a few measurement settings. Our new method is general enough to allow for measurements from a continuous family, and is also applicable to continuous-variable states. As a technical result, this work generalizes quantum compressed sensing to the situation where the measured observables are taken from a so-called tight frame (rather than an orthonormal basis) --- hence covering most realistic measurement scenarios. As an application, we discuss the reconstruction of quantum states of light from homodyne detection and other types of measurements, and we present simulations that show the advantage of the proposed compressed sensing technique over present methods. Finally, we introduce a method to construct a certificate which guarantees the success of the reconstruction with no assumption on the state, and we show how slightly more measurements give rise to "universal" state reconstruction that is highly robust to noise.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Negative Quasi-Probability as a Resource for Quantum Computation

A central problem in quantum information is to determine the minimal physical resources that are required for quantum computational speedup and, in particular, for fault-tolerant quantum computation. We establish a remarkable connection between the potential for quantum speed-up and the onset of negative values in a distinguished quasi-probability representation, a discrete analog of the Wigner function for quantum systems of odd dimension. This connection allows us to resolve an open question on the existence of bound states for magic-state distillation: we prove that there exist mixed states outside the convex hull of stabilizer states that cannot be distilled to non-stabilizer target states using stabilizer operations. We also provide an efficient simulation protocol for Clifford circuits that extends to a large class of mixed states, including bound universal states.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Pinning of Fermionic Occupation Numbers

The Pauli exclusion principle is a constraint on the natural occupation numbers of fermionic states. It has been suspected since at least the 1970's, and only proved very recently, that there is a multitude of further constraints on these numbers, generalizing the Pauli principle. Here, we provide the first analytic analysis of the physical relevance of these constraints. We compute the natural occupation numbers for the ground states of a family of interacting fermions in a harmonic potential. Intriguingly, we find that the occupation numbers are almost, but not exactly, pinned to the boundary of the allowed region (quasi-pinned). The result suggests that the physics behind the phenomenon is richer than previously appreciated. In particular, it shows that for some models, the generalized Pauli constraints play a role for the ground state, even though they do not limit the ground-state energy. Our findings suggest a generalization of the Hartree-Fock approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators

Intuitively, if a density operator has small rank, then it should be easier to estimate from experimental data, since in this case only a few eigenvectors need to be learned. We prove two complementary results that confirm this intuition. First, we show that a low-rank density matrix can be estimated using fewer copies of the state, i.e., the sample complexity of tomography decreases with the rank. Second, we show that unknown low-rank states can be reconstructed from an incomplete set of measurements, using techniques from compressed sensing and matrix completion. These techniques use simple Pauli measurements, and their output can be certified without making any assumptions about the unknown state. We give a new theoretical analysis of compressed tomography, based on the restricted isometry property (RIP) for low-rank matrices. Using these tools, we obtain near-optimal error bounds, for the realistic situation where the data contains noise due to finite statistics, and the density matrix is full-rank with decaying eigenvalues. We also obtain upper-bounds on the sample complexity of compressed tomography, and almost-matching lower bounds on the sample complexity of any procedure using adaptive sequences of Pauli measurements. Using numerical simulations, we compare the performance of two compressed sensing estimators with standard maximum-likelihood estimation (MLE). We find that, given comparable experimental resources, the compressed sensing estimators consistently produce higher-fidelity state reconstructions than MLE. In addition, the use of an incomplete set of measurements leads to faster classical processing with no loss of accuracy. Finally, we show how to certify the accuracy of a low rank estimate using direct fidelity estimation and we describe a method for compressed quantum process tomography that works for processes with small Kraus rank.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Permutationally invariant quantum tomography

We present a scalable method for the tomography of large multiqubit quantum registers. It acquires information about the permutationally invariant part of the density operator, which is a good approximation to the true state in many, relevant cases. Our method gives the best measurement strategy to minimize the experimental effort as well as the uncertainties of the reconstructed density matrix. We apply our method to the experimental tomography of a photonic four-qubit symmetric Dicke state.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

All reversible dynamics in maximally non-local theories are trivial

A remarkable feature of quantum theory is non-locality (i.e. the presence of correlations which violate Bell inequalities). However, quantum correlations are not maximally non-local, and it is natural to ask whether there are compelling reasons for rejecting theories in which stronger violations are possible. To shed light on this question, we consider post-quantum theories in which maximally non-local states (non-local boxes) occur. It has previously been conjectured that the set of dynamical transformations possible in such theories is severely limited. We settle the question affirmatively in the case of reversible dynamics, by completely characterizing all such transformations allowed in this setting. We find that the dynamical group is trivial, in the sense that it is generated solely by local operations and permutations of systems. In particular, no correlations can ever be created; non-local boxes cannot be prepared from product states (in other words, no analogues of entangling unitary operations exist), and classical computers can efficiently simulate all such processes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Concentration of measure for quantum states with a fixed expectation value

Given some observable H of a finite-dimensional quantum system, we investigate the typical properties of random quantum state vectors that have a fixed expectation value with respect to H. Under some some conditions on the spectrum, we prove that this manifold of quantum states shows a concentration of measure phenomenon: any continuous function on this set is almost everywhere close to its mean. We also give a method to estimate the corresponding expectation values analytically, and we prove a formula for the typical reduced density matrix in the case that H is a sum of local observables. We discuss the implications of our results as new proof tools in quantum information theory and to study phenomena in quantum statistical mechanics. As a by-product, we derive a method to sample the resulting distribution numerically, which generalizes the well-known Gaussian method to draw random states from the sphere.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Heralded Polynomial-Time Quantum State Tomography

We describe an algorithm for quantum state tomography that converges in polynomial time to an estimate, together with a rigorous error bound on the fidelity between the estimate and the true state. The result suggests that state tomography on large quantum systems may be much more feasible than the exponential size of state space suggests. In many situations, the correctness of the state estimate can be certified from the data alone, with no a priori assumptions on the form of the measured state.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Note on sampling without replacing from a finite collection of matrices

This technical note supplies an affirmative answer to a question raised in a recent pre-print [arXiv:0910.1879] in the context of a "matrix recovery" problem. Assume one samples m Hermitian matrices X_1, ..., X_m with replacement from a finite collection. The deviation of the sum X_1+...+X_m from its expected value in terms of the operator norm can be estimated by an "operator Chernoff-bound" due to Ahlswede and Winter. The question arose whether the bounds obtained this way continue to hold if the matrices are sampled without replacement. We remark that a positive answer is implied by a classical argument by Hoeffding. Some consequences for the matrix recovery problem are sketched.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Probing the negative Wigner function of a pulsed single photon point by point

We investigate quantum properties of pulsed light fields point by point in phase space. We probe the negative region of the Wigner function of a single photon generated by the means of waveguided parametric down-conversion. This capability is achieved by employing loss-tolerant photon-number resolving detection, allowing us to directly observe the oscillations of the photon statistics in dependence of applied displacements in phase space. Our scheme is highly mode sensitive and can reveal the single-mode character of the signal state.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Quantum state tomography via compressed sensing

We establish methods for quantum state tomography based on compressed sensing. These methods are specialized for quantum states that are fairly pure, and they offer a significant performance improvement on large quantum systems. In particular, they are able to reconstruct an unknown density matrix of dimension d and rank r using O(rd log^2 d) measurement settings, compared to standard methods that require d^2 settings. Our methods have several features that make them amenable to experimental implementation: they require only simple Pauli measurements, use fast convex optimization, are stable against noise, and can be applied to states that are only approximately low-rank. The acquired data can be used to certify that the state is indeed close to pure, so no a priori assumptions are needed. We present both theoretical bounds and numerical simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Recovering low-rank matrices from few coefficients in any basis

We present novel techniques for analyzing the problem of low-rank matrix recovery. The methods are both considerably simpler and more general than previous approaches. It is shown that an unknown (n x n) matrix of rank r can be efficiently reconstructed from only O(n r nu log^2 n) randomly sampled expansion coefficients with respect to any given matrix basis. The number nu quantifies the "degree of incoherence" between the unknown matrix and the basis. Existing work concentrated mostly on the problem of "matrix completion" where one aims to recover a low-rank matrix from randomly selected matrix elements. Our result covers this situation as a special case. The proof consists of a series of relatively elementary steps, which stands in contrast to the highly involved methods previously employed to obtain comparable results. In cases where bounds had been known before, our estimates are slightly tighter. We discuss operator bases which are incoherent to all low-rank matrices simultaneously. For these bases, we show that O(n r nu log n) randomly sampled expansion coefficients suffice to recover any low-rank matrix with high probability. The latter bound is tight up to multiplicative constants.

0 citations0 reviewsNo code linkedOpen access