Search

We present a robust shadow estimation protocol for wide classes of shallow measurement circuits that mitigates noise as long as the effective measurement map is locally unitarily invariant. This is in practice an excellent approximation, encompassing for instance the case of ideal single-qubit Clifford gates composing the first circuit layer of an otherwise arbitrary circuit architecture and even non-Markovian, gate-dependent noise in the rest of the circuit. We argue that for approximately local noise the measurement channel has an efficient matrix-product (tensor-train) representation, and show how to estimate this directly from experimental data using tensor-network tools, eliminating the need for analytical or numeric calculations. We illustrate the relevance of our method with both numerics and proof-of-principle experiments on an IBM Q device. Numerically, we show that, while unmitigated shallow shadows with noisy circuits become more biased as the depth increases, robust ones become more accurate for relevant parameter regimes. Experimentally, we observe major bias reductions in two simple fidelity estimation tasks using 5-qubit circuits with up to 2 layers of entangling gates using the mitigated variant, of close to an order of magnitude for $10^4$ measurement shots, e.g. Under the practical constraints of current and near-term noisy quantum devices, our method maximally realizes the potential of shadow estimation with global rotations., Comment: 11 pages, 9 figures

Expectation values of observables are routinely estimated using so-called classical shadows$\unicode{x2014}$the outcomes of randomized bases measurements on a repeatedly prepared quantum state. In order to trust the accuracy of shadow estimation in practice, it is crucial to understand the behavior of the estimators under realistic noise. In this work, we prove that any shadow estimation protocol involving Clifford unitaries is stable under gate-dependent noise for observables with bounded stabilizer norm$\unicode{x2014}$originally introduced in the context of simulating Clifford circuits. For these observables, we also show that the protocol's sample complexity is essentially identical to the noiseless case. In contrast, we demonstrate that estimation of `magic' observables can suffer from a bias that scales exponentially in the system size. We further find that so-called robust shadows, aiming at mitigating noise, can introduce a large bias in the presence of gate-dependent noise compared to unmitigated classical shadows. Nevertheless, we guarantee the functioning of robust shadows for a more general noise setting than in previous works. On a technical level, we identify average noise channels that affect shadow estimators and allow for a more fine-grained control of noise-induced biases., Comment: 26 pages, 1 figure; v2: Improved presentation of results in the main text

We present Qibolab, an open-source software library for quantum hardware control integrated with the Qibo quantum computing middleware framework. Qibolab provides the software layer required to automatically execute circuit-based algorithms on custom self-hosted quantum hardware platforms. We introduce a set of objects designed to provide programmatic access to quantum control through pulses-oriented drivers for instruments, transpilers and optimization algorithms. Qibolab enables experimentalists and developers to delegate all complex aspects of hardware implementation to the library so they can standardize the deployment of quantum computing algorithms in a extensible hardware-agnostic way, using superconducting qubits as the first officially supported quantum technology. We first describe the status of all components of the library, then we show examples of control setup for superconducting qubits platforms. Finally, we present successful application results related to circuit-based algorithms., Comment: 20 pages, 9 figures, accepted in Quantum, code available at https://github.com/qiboteam/qibolab

A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight $M$ of the penalty terms. Classically known as the "Big-$M$" problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$ and establishing bounds on the Hamiltonian spectral gap $\Delta$, inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of $\Delta$ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike., Comment: 11 pages, 3 figures

In this proceedings we present Qibocal, an open-source software package for calibration and characterization of quantum processing units (QPUs) based on the Qibo framework. Qibocal is specifically designed for self-hosted QPUs and provides the groundwork to easily develop, deploy and distribute characterization and calibration routines for all levels of hardware abstraction. Qibocal is based on a modular QPU platform agnostic approach and it provides a general purpose toolkit for superconducting qubits with the possibility of extensions to other quantum technologies. After motivating the need for such a module, we explain the program's flow and show examples of actual use for QPU calibration. We also showcase additional features provided by the library including automatic report generation and live plotting., Comment: 7 pages, 4 figures, ACAT22 proceedings

In its many variants, randomized benchmarking (RB) is a broadly used technique for assessing the quality of gate implementations on quantum computers. A detailed theoretical understanding and general guarantees exist for the functioning and interpretation of RB protocols if the gates under scrutiny are drawn uniformly at random from a compact group. In contrast, many practically attractive and scalable RB protocols implement random quantum circuits with local gates randomly drawn from some gate-set. Despite their abundance in practice, for those non-uniform RB protocols, general guarantees for gates from arbitrary compact groups under experimentally plausible assumptions are missing. In this work, we derive such guarantees for a large class of RB protocols for random circuits that we refer to as filtered RB. Prominent examples include linear cross-entropy benchmarking, character benchmarking, Pauli-noise tomography and variants of simultaneous RB. Building upon recent results for random circuits, we show that many relevant filtered RB schemes can be realized with random quantum circuits in linear depth, and we provide explicit small constants for common instances. We further derive general sample complexity bounds for filtered RB. We show filtered RB to be sample-efficient for several relevant groups, including protocols addressing higher-order cross-talk. Our theory for non-uniform filtered RB is, in principle, flexible enough to design new protocols for non-universal and analog quantum simulators., Comment: 59 pages, 5 figures. Accepted for a talk at QIP 2023. v3: more accessible overview of results and high-level discussion; improved structure and readability

Properties of quantum systems can be estimated using classical shadows, which implement measurements based on random ensembles of unitaries. Originally derived for global Clifford unitaries and products of single-qubit Clifford gates, practical implementations are limited to the latter scheme for moderate numbers of qubits. Beyond local gates, the accurate implementation of very short random circuits with two-local gates is still experimentally feasible and, therefore, interesting for implementing measurements in near-term applications. In this work, we derive closed-form analytical expressions for shadow estimation using brickwork circuits with two layers of parallel two-local Haar-random (or Clifford) unitaries. Besides the construction of the classical shadow, our results give rise to sample-complexity guarantees for estimating Pauli observables. We then compare the performance of shadow estimation with brickwork circuits to the established approach using local Clifford unitaries and find improved sample complexity in the estimation of observables supported on sufficiently many qubits., Comment: 15+12 pages, several figures; v2: small improvements and new examples. Close to published version

The bi-sparse blind deconvolution problem is studied -- that is, from the knowledge of $h*(Qb)$, where $Q$ is some linear operator, recovering $h$ and $b$, which are both assumed to be sparse. The approach rests upon lifting the problem to a linear one, and then applying the hierarchical sparsity framework. In particular, the efficient HiHTP algorithm is proposed for performing the recovery. Then, under a random model on the matrix $Q$, it is theoretically shown that an $s$-sparse $h \in \mathbb{K}^\mu$ and $\sigma$-sparse $b \in \mathbb{K}^n$ with high probability can be recovered when $\mu \succcurlyeq s\log(s)^2\log(\mu)\log(\mu n) + s\sigma \log(n)$., Comment: V2: Completely revised version, entirely different proof, resulting in the recovery guarantee improved by a factor s

The physics of a closed quantum mechanical system is governed by its Hamiltonian. However, in most practical situations, this Hamiltonian is not precisely known, and ultimately all there is are data obtained from measurements on the system. In this work, we introduce a highly scalable, data-driven approach to learning families of interacting many-body Hamiltonians from dynamical data, by bringing together techniques from gradient-based optimization from machine learning with efficient quantum state representations in terms of tensor networks. Our approach is highly practical, experimentally friendly, and intrinsically scalable to allow for system sizes of above 100 spins. In particular, we demonstrate on synthetic data that the algorithm works even if one is restricted to one simple initial state, a small number of single-qubit observables, and time evolution up to relatively short times. For the concrete example of the one-dimensional Heisenberg model our algorithm exhibits an error constant in the system size and scaling as the inverse square root of the size of the data set., Comment: 11 pages, 5 figures

It was recently observed that in certain thermalizing many-body systems, measuring the complement of a subsystem that thermalized to infinite temperature in a suitable orthonormal basis gives rise to approximate quantum state k-designs as post-measurement states on the subsystem. We prove that this emergence of approximate k-designs holds true in every large system where some small subsystem is close to being maximally mixed. On a technical level we show that any high-dimensional purification of an approximately maximally mixed state induces an approximate quantum state k-design when measured in a suitable orthonormal basis. Moreover, we show that this is true with overwhelming probability for measurement bases chosen uniformly at random from the Haar measure., Comment: 4+6 pages

Flexible characterization techniques that identify and quantify experimental imperfections under realistic assumptions are crucial for the development of quantum computers. Gate set tomography is a characterization approach that simultaneously and self-consistently extracts a tomographic description of the implementation of an entire set of quantum gates, as well as the initial state and measurement, from experimental data. Obtaining such a detailed picture of the experimental implementation is associated with high requirements on the number of sequences and their design, making gate set tomography a challenging task even for only two qubits. In this work, we show that low-rank approximations of gate sets can be obtained from significantly fewer gate sequences and that it is sufficient to draw them randomly. Such tomographic information is needed for the crucial task of dealing with coherent noise. To this end, we formulate the data processing problem of gate set tomography as a rank-constrained tensor completion problem. We provide an algorithm to solve this problem while respecting the usual positivity and normalization constraints of quantum mechanics by using second-order geometrical optimization methods on the complex Stiefel manifold. Besides the reduction in sequences, we demonstrate numerically that the algorithm does not rely on structured gate sets or an elaborate circuit design to robustly perform gate set tomography. Therefore, it is more flexible than traditional approaches. We also demonstrate how coherent errors in shadow estimation protocols can be mitigated using estimates from gate set tomography., Comment: 14+12 pages, several figures and diagrams; v2: An error in our interface to pyGSTi has been corrected and Sections IV.A and IV.B have been reworked; v3: Added a new section on noise mitigation for shadow estimation with compressive GST, a corresponding appendix, an improved runtime table and various clarifications

The blind deconvolution problem amounts to reconstructing both a signal and a filter from the convolution of these two. It constitutes a prominent topic in mathematical and engineering literature. In this work, we analyze a sparse version of the problem: The filter $h\in \mathbb{R}^\mu$ is assumed to be $s$-sparse, and the signal $b \in \mathbb{R}^n$ is taken to be $\sigma$-sparse, both supports being unknown. We observe a convolution between the filter and a linear transformation of the signal. Motivated by practically important multi-user communication applications, we derive a recovery guarantee for the simultaneous demixing and deconvolution setting. We achieve efficient recovery by relaxing the problem to a hierarchical sparse recovery for which we can build on a flexible framework. At the same time, for this we pay the price of some sub-optimal guarantees compared to the number of free parameters of the problem. The signal model we consider is sufficiently general to capture many applications in a number of engineering fields. Despite their practical importance, we provide first rigorous performance guarantees for efficient and simple algorithms for the bi-sparse and generalized demixing setting. We complement our analytical results by presenting results of numerical simulations. We find evidence that the sub-optimal scaling $s^2\sigma \log(\mu)\log(n)$ of our derived sufficient condition is likely overly pessimistic and that the observed performance is better described by a scaling proportional to $ s\sigma$ up to log-factors., Comment: 6 pages, 5 figures

The required precision to perform quantum simulations beyond the capabilities of classical computers imposes major experimental and theoretical challenges. The key to solving these issues are precise means of characterizing analog quantum simulators. Here, we robustly estimate the free Hamiltonian parameters of bosonic excitations in a superconducting-qubit analog quantum simulator from measured time-series of single-mode canonical coordinates. We achieve high levels of precision in estimating the Hamiltonian parameters by exploiting a priori knowledge, making it robust against noise and state-preparation and measurement (SPAM) errors. Importantly, we are also able to obtain tomographic information about those SPAM errors from the same data, crucial for the experimental applicability of Hamiltonian learning in dynamical quantum-quench experiments. Our learning algorithm is scalable both in terms of the required amounts of data and post-processing. To achieve this, we develop a new super-resolution technique coined tensorESPRIT for frequency extraction from matrix time-series. The algorithm then combines tensorESPRIT with constrained manifold optimization for the eigenspace reconstruction with pre- and post-processing stages. For up to 14 coupled superconducting qubits on two Sycamore processors, we identify the Hamiltonian parameters -- verifying the implementation on one of them up to sub-MHz precision -- and construct a spatial implementation error map for a grid of 27 qubits. Our results constitute an accurate implementation of a dynamical quantum simulation that is characterized using a new diagnostic toolkit for understanding, calibrating, and improving analog quantum processors., Comment: 13+18 pages, 7+7 figures. v2: Substantial method development (tensorESPRIT), additional large-scale data and numerical benchmarking added + 18 pages of SM; JF added as author. v3: presentation improved

A new family of operators, coined hierarchical measurement operators, is introduced and discussed within the well-known hierarchical sparse recovery framework. Such operator is a composition of block and mixing operations and notably contains the Kronecker product as a special case. Results on their hierarchical restricted isometry property (HiRIP) are derived, generalizing prior work on recovery of hierarchically sparse signals from Kronecker-structured linear measurements. Specifically, these results show that, very surprisingly, sparsity properties of the block and mixing part can be traded against each other. The measurement structure is well-motivated by a massive random access channel design in communication engineering. Numerical evaluation of user detection rates demonstrate the huge benefit of the theoretical framework., Comment: 5 pages, 2 figures. arXiv admin note: text overlap with arXiv:2005.10379

Compressed sensing is a paradigm within signal processing that provides the means for recovering structured signals from linear measurements in a highly efficient manner. Originally devised for the recovery of sparse signals, it has become clear that a similar methodology would also carry over to a wealth of other classes of structured signals. In this work, we provide an overview over the theory of compressed sensing for a particularly rich family of such signals, namely those of hierarchically structured signals. Examples of such signals are constituted by blocked vectors, with only few non-vanishing sparse blocks. We present recovery algorithms based on efficient hierarchical hard-thresholding. The algorithms are guaranteed to converge, in a stable fashion both with respect to measurement noise as well as to model mismatches, to the correct solution provided the measurement map acts isometrically restricted to the signal class. We then provide a series of results establishing the required condition for large classes of measurement ensembles. Building upon this machinery, we sketch practical applications of this framework in machine-type communications and quantum tomography., Comment: This book chapter is a report on findings within the DFG-funded priority program `Compressed Sensing in Information Processing' (CoSIP)

The study of generic properties of quantum states has led to an abundance of insightful results. A meaningful set of states that can be efficiently prepared in experiments are ground states of gapped local Hamiltonians, which are well approximated by matrix product states. In this work, we introduce a picture of generic states within the trivial phase of matter with respect to their non-equilibrium and entropic properties: We do so by rigorously exploring non-translation-invariant matrix product states drawn from a local i.i.d. Haar-measure. We arrive at these results by exploiting techniques for computing moments of random unitary matrices and by exploiting a mapping to partition functions of classical statistical models, a method that has lead to valuable insights on local random quantum circuits. Specifically, we prove that such disordered random matrix product states equilibrate exponentially well with overwhelming probability under the time evolution of Hamiltonians featuring a non-degenerate spectrum. Moreover, we prove two results about the entanglement Renyi entropy: The entropy with respect to sufficiently disconnected subsystems is generically extensive in the system-size, and for small connected systems the entropy is almost maximal for sufficiently large bond dimensions., Comment: 11 pages

Randomized benchmarking (RB) refers to a collection of protocols that in the past decade have become central methods for characterizing quantum gates. These protocols aim at efficiently estimating the quality of a set of quantum gates in a way that is resistant to state preparation and measurement errors. Over the years many versions have been developed, however, a comprehensive theoretical treatment of RB has been missing. In this work, we develop a rigorous framework of RB general enough to encompass virtually all known protocols as well as novel, more flexible extensions. Overcoming previous limitations on error models and gate sets, this framework allows us, for the first time, to formulate realistic conditions under which we can rigorously guarantee that the output of any RB experiment is well-described by a linear combination of matrix exponential decays. We complement this with a detailed analysis of the fitting problem associated with RB data. We introduce modern signal processing techniques to RB, prove analytical sample complexity bounds, and numerically evaluate performance and limitations. In order to reduce the resource demands of this fitting problem, we introduce novel, scalable post-processing techniques to isolate exponential decays, significantly improving the practical feasibility of a large set of RB protocols. These post-processing techniques overcome shortcomings in efficiency of several previously proposed methods such as character benchmarking and linear-cross entropy benchmarking. Finally, we discuss, in full generality, how and when RB decay rates can be used to infer quality measures like the average fidelity. On the technical side, our work substantially extends the recently developed Fourier-theoretic perspective on RB by making use of the perturbation theory of invariant subspaces, as well as ideas from signal processing., Comment: 61 pages, 7 figures, replaced by final version in PRX Quantum

The precise control of complex quantum systems promises numerous technological applications including digital quantum computing. The complexity of such devices renders the certification of their correct functioning a challenge. To address this challenge, numerous methods were developed in the last decade. In this tutorial, we explain prominent protocols for certifying the physical layer of quantum devices described by quantum states and processes. Such protocols are particularly important in the development of near-term devices. Specifically, we discuss methods of direct quantum state certification, direct fidelity estimation, shadow fidelity estimation, direct quantum process certification, randomized benchmarking and cross-entropy benchmarking. Moreover, we provide an introduction to powerful mathematical methods, which are widely used in quantum information theory, in order to derive theoretical guarantees for the protocols., Comment: 47 pages, 4 figures, 62 Theorems, Propositions, Lemma, Protocols, Definitions and Examples; v2: published version with numerous small improvements; v3: the argument leading to the diamond norm normalization of quantum channels has been corrected

Extracting tomographic information about quantum states is a crucial task in the quest towards devising high-precision quantum devices. Current schemes typically require measurement devices for tomography that are a priori calibrated to high precision. Ironically, the accuracy of the measurement calibration is fundamentally limited by the accuracy of state preparation, establishing a vicious cycle. Here, we prove that this cycle can be broken and the dependence on the measurement device's calibration significantly relaxed. We show that exploiting the natural low-rank structure of quantum states of interest suffices to arrive at a highly scalable `blind' tomography scheme with a classically efficient post-processing algorithm. We further improve the efficiency of our scheme by making use of the sparse structure of the calibrations. This is achieved by relaxing the blind quantum tomography problem to the de-mixing of a sparse sum of low-rank matrices. We prove that the proposed algorithm recovers a low-rank quantum state and the calibration provided that the measurement model exhibits a restricted isometry property. For generic measurements, we show that it requires a close-to-optimal number of measurement settings. Complementing these conceptual and mathematical insights, we numerically demonstrate that robust blind quantum tomography is possible in a practical setting inspired by an implementation of trapped ions., Comment: 30 pages, 9 Figures

A new class of measurement operators, coined hierarchical measurement operators, and prove results guaranteeing the efficient, stable and robust recovery of hierarchically structured signals from such measurements. We derive bounds on their hierarchical restricted isometry properties based on the restricted isometry constants of their constituent matrices, generalizing and extending prior work on Kronecker-product measurements. As an exemplary application, we apply the theory to two communication scenarios. The fast and scalable HiHTP algorithm is shown to be suitable for solving these types of problems and its performance is evaluated numerically in terms of sparse signal recovery and block detection capability., Comment: 22 pages, 5 figures. v3: Significant rework of previous version. Section on incoherent blocks added, as well as more numerical experiments. v4: Revision of the manuscript. Several previous mistakes have been corrected

Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full $n$-qubit group, one often resorts to $t$-designs. Unitary $t$-designs mimic the Haar-measure up to $t$-th moments. It is known that Clifford operations can implement at most $3$-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject $O(t^{4}\log^{2}(t)\log(1/\varepsilon))$ many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an $\varepsilon$-approximate $t$-design. Strikingly, the number of non-Clifford gates required is independent of the system size -- asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the $t$-th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators., Comment: v3: version published in Communications in Mathematical Physics, title changed; v2: improved presentation, added consequences of the main result and fixed typos; 46 pages, 1 figure

Quantum Monte Carlo (QMC) methods are the gold standard for studying equilibrium properties of quantum many-body systems -- their phase transitions, ground and thermal state properties. However, in many interesting situations QMC methods are faced with a sign problem, causing the severe limitation of an exponential increase in the sampling complexity and hence the run-time of the QMC algorithm. In this work, we develop a systematic, generally applicable, and practically feasible methodology for easing the sign problem by efficiently computable basis changes and use it to rigorously assess the sign problem. Our framework introduces measures of non-stoquasticity that -- as we demonstrate analytically and numerically -- at the same time provide a practically relevant and efficiently computable figure of merit for the severity of the sign problem. We show that those measures can practically be brought to a good use to ease the sign problem. To do so, we use geometric algorithms for optimization over the orthogonal group and ease the sign problem of frustrated Heisenberg ladders. Complementing this pragmatic mindset, we prove that easing the sign problem in terms of those measures is in general an NP-complete task for nearest-neighbour Hamiltonians and simple basis choices by a polynomial reduction to the MAXCUT-problem. Intriguingly, easing remains hard even in cases in which we can efficiently assert that no exact solution exists., Comment: 20+7 pages, 8 figures. Comments welcome. v2: added Theorem 6 on efficiently computing the non-stoquasticity. v3: minor clarifications

Recently, a new class of so-called \emph{hierarchical thresholding algorithms} was introduced to optimally exploit the sparsity structure in joint user activity and channel detection problems. In this paper, we take a closer look at the user detection performance of such algorithms under noise and relate its performance to the classical block correlation detector with orthogonal signatures. More specifically, we derive a lower bound for the diversity order which, under suitable choice of the signatures, equals that of the block correlation detector. Surprisingly, in specific parameter settings non-orthogonal pilots, i.e. pilots where (cyclically) shifted versions interfere with each other, outperform the block correlation detector. Altogether, we show that, in wide parameter regimes, the hierarchical thresholding detectors behave like the classical correlator with improved detection performance but operate with much less required pilot subcarriers. We provide mathematically rigorous and easy to handle formulas for numerical evaluations and system design. Finally, we evaluate our findings with numerical examples and show that, in a practical parameter setting, a classical pilot channel can accommodate up to three advanced pilot channels with the same performance., Comment: 15 pages, 12 figures

The problem of excessive pilot overhead required for uplink massive MIMO channel estimation is well known, let alone when it is considered along with wideband (OFDM) transmissions. Towards channel estimators that are both efficient and require low-training overhead, compressive sensing (CS) approaches have been increasingly popular, exploiting the sparse nature of the physical channel. However, no analytical insights regarding the overhead required for reliable channel estimation in wideband massive MIMO are available. By observing that the wideband massive MIMO channel can be represented by a vector that is not simply sparse but has well defined structural properties, referred to as hierarchical sparsity, we propose low complexity channel estimators for the multiuser scenario that take this property into account. By employing the framework of the hierarchical restricted isometry property, rigorous performance guarantees for these algorithms are provided suggesting concrete design goals for the user pilot sequences. For a specific design, we analytically characterize the scaling of the required pilot overhead with increasing number of antennas and bandwidth, revealing that, as long as the number of antennas is sufficiently large, it is independent of the per user channel sparsity level as well as the number of active users. Hence, surprisingly, in contrast to the classical setting, pilot overhead can be shifted into spatial dimensions not affecting crucial bandwidth constraints thereby increasing the overall system capacity. These analytical insights are verified by simulation results demonstrating also the superiority of the proposed algorithm over conventional CS algorithms that ignore the hierarchical sparsity property., Comment: 14 two-column pages; submitted to IEEE Trans. Wireless Commun

The problem of wideband massive MIMO channel estimation is considered. Targeting for low complexity algorithms as well as small training overhead, a compressive sensing (CS) approach is pursued. Unfortunately, due to the Kronecker-type sensing (measurement) matrix corresponding to this setup, application of standard CS algorithms and analysis methodology does not apply. By recognizing that the channel possesses a special structure, termed hierarchical sparsity, we propose an efficient algorithm that explicitly takes into account this property. In addition, by extending the standard CS analysis methodology to hierarchical sparse vectors, we provide a rigorous analysis of the algorithm performance in terms of estimation error as well as number of pilot subcarriers required to achieve it. Small training overhead, in turn, means higher number of supported users in a cell and potentially improved pilot decontamination. We believe, that this is the first paper that draws a rigorous connection between the hierarchical framework and Kronecker measurements. Numerical results verify the advantage of employing the proposed approach in this setting instead of standard CS algorithms., Comment: 8 pages, 5 figures

Characterising quantum processes is a key task in and constitutes a challenge for the development of quantum technologies, especially at the noisy intermediate scale of today's devices. One method for characterising processes is randomised benchmarking, which is robust against state preparation and measurement (SPAM) errors, and can be used to benchmark Clifford gates. A complementing approach asks for full tomographic knowledge. Compressed sensing techniques achieve full tomography of quantum channels essentially at optimal resource efficiency. So far, guarantees for compressed sensing protocols rely on unstructured random measurements and can not be applied to the data acquired from randomised benchmarking experiments. It has been an open question whether or not the favourable features of both worlds can be combined. In this work, we give a positive answer to this question. For the important case of characterising multi-qubit unitary gates, we provide a rigorously guaranteed and practical reconstruction method that works with an essentially optimal number of average gate fidelities measured respect to random Clifford unitaries. Moreover, for general unital quantum channels we provide an explicit expansion into a unitary 2-design, allowing for a practical and guaranteed reconstruction also in that case. As a side result, we obtain a new statistical interpretation of the unitarity -- a figure of merit that characterises the coherence of a process. In our proofs we exploit recent representation theoretic insights on the Clifford group, develop a version of Collins' calculus with Weingarten functions for integration over the Clifford group, and combine this with proof techniques from compressed sensing., Comment: 26 pages, 3 figures. V2: Incomplete funding information corrected and minor improvements of the presentation

One of the outstanding problems in non-equilibrium physics is to precisely understand when and how physically relevant observables in many-body systems equilibrate under unitary time evolution. General equilibration results show that equilibration is generic provided that the initial state has overlap with sufficiently many energy levels. But results not referring to typicality which show that natural initial states actually fulfill this condition are lacking. In this work, we present stringent results for equilibration for systems in which Renyi entanglement entropies in energy eigenstates with finite energy density are extensive for at least some, not necessarily connected, sub-system. Our results reverse the logic of common arguments, in that we derive equilibration from a weak condition akin to the eigenstate thermalization hypothesis, which is usually attributed to thermalization in systems that are assumed to equilibrate in the first place. We put the findings into the context of studies of many-body localization and many-body scars., Comment: 6+8 pages; v3: improved presentation, close to published version

The Internet of Things and specifically the Tactile Internet give rise to significant challenges for notions of security. In this work, we introduce a novel concept for secure massive access. The core of our approach is a fast and low-complexity blind deconvolution algorithm exploring a bi-linear and hierarchical compressed sensing framework. We show that blind deconvolution has two appealing features: 1) There is no need to coordinate the pilot signals, so even in the case of collisions in user activity, the information messages can be resolved. 2) Since all the individual channels are recovered in parallel, and by assumed channel reciprocity, the measured channel entropy serves as a common secret and is used as an encryption key for each user. We will outline the basic concepts underlying the approach and describe the blind deconvolution algorithm in detail. Eventually, simulations demonstrate the ability of the algorithm to recover both channel and message. They also exhibit the inherent trade-offs of the scheme between economical recovery and secret capacity., Comment: submitted to WCNC2018 (accepted)

We propose and analyze a solution to the problem of recovering a block sparse signal with sparse blocks from linear measurements. Such problems naturally emerge inter alia in the context of mobile communication, in order to meet the scalability and low complexity requirements of massive antenna systems and massive machine-type communication. We introduce a new variant of the Hard Thresholding Pursuit (HTP) algorithm referred to as HiHTP. We provide both a proof of convergence and a recovery guarantee for noisy Gaussian measurements that exhibit an improved asymptotic scaling in terms of the sampling complexity in comparison with the usual HTP algorithm. Furthermore, hierarchically sparse signals and Kronecker product structured measurements naturally arise together in a variety of applications. We establish the efficient reconstruction of hierarchically sparse signals from Kronecker product measurements using the HiHTP algorithm. Additionally, we provide analytical results that connect our recovery conditions to generalized coherence measures. Again, our recovery results exhibit substantial improvement in the asymptotic sampling complexity scaling over the standard setting. Finally, we validate in numerical experiments that for hierarchically sparse signals, HiHTP performs significantly better compared to HTP., Comment: 11+4 pages, 5 figures. V3: Incomplete funding information corrected and minor typos corrected. V4: Change of title and additional author Axel Flinth. Included new results on Kronecker product measurements and relations of HiRIP to hierarchical coherence measures. Improved presentation of general hierarchically sparse signals and correction of minor typos