TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Fri, 24 Mar 2023 22:46:00 GMT2023-03-24T22:46:00Z50351Optimal noise estimation from syndrome statistics of quantum codeshttp://hdl.handle.net/11420/13931Title: Optimal noise estimation from syndrome statistics of quantum codes
Authors: Wagner, Thomas; Kampermann, Hermann; Bruß, Dagmar; Kliesch, Martin
Abstract: Quantum error correction allows to actively correct errors occurring in a quantum computation when the noise is weak enough. To make this error correction competitive information about the specific noise is required. Traditionally, this information is obtained by benchmarking the device before operation. We address the question of what can be learned from only the measurements done during decoding. Such estimation of noise models was proposed for surface codes, exploiting their special structure, and in the limit of low error rates also for other codes. However, so far it has been unclear under what general conditions noise models can be estimated from the syndrome measurements. In this work, we derive a general condition for identifiability of the error rates. For general stabilizer codes, we prove identifiability under the assumption that the rates are small enough. Without this assumption we prove a result for perfect codes. Finally, we propose a practical estimation method with linear runtime for concatenated codes. We demonstrate that it outperforms other recently proposed methods and that the estimation is optimal in the sense that it reaches the Cramér-Rao Bound. Our method paves the way for practical calibration of error corrected quantum devices during operation.
Wed, 31 Mar 2021 00:00:00 GMThttp://hdl.handle.net/11420/139312021-03-31T00:00:00ZTheory of quantum system certificationhttp://hdl.handle.net/11420/13932Title: Theory of quantum system certification
Authors: Kliesch, Martin; Roth, Ingo
Abstract: 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.
Fri, 29 Jan 2021 00:00:00 GMThttp://hdl.handle.net/11420/139322021-01-29T00:00:00ZTraining variational quantum algorithms Is NP-hardhttp://hdl.handle.net/11420/13620Title: Training variational quantum algorithms Is NP-hard
Authors: Bittel, Lennart; Kliesch, Martin
Abstract: Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.
Fri, 17 Sep 2021 00:00:00 GMThttp://hdl.handle.net/11420/136202021-09-17T00:00:00ZSample Complexity of Device-Independently Certified "quantum Supremacy"http://hdl.handle.net/11420/14073Title: Sample Complexity of Device-Independently Certified "quantum Supremacy"
Authors: Hangleiter, Dominik; Kliesch, Martin; Eisert, Jens; Gogolin, Christian
Abstract: Results on the hardness of approximate sampling are seen as important stepping stones toward a convincing demonstration of the superior computational power of quantum devices. The most prominent suggestions for such experiments include boson sampling, instantaneous quantum polynomial time (IQP) circuit sampling, and universal random circuit sampling. A key challenge for any such demonstration is to certify the correct implementation. For all these examples, and in fact for all sufficiently flat distributions, we show that any noninteractive certification from classical samples and a description of the target distribution requires exponentially many uses of the device. Our proofs rely on the same property that is a central ingredient for the approximate hardness results, namely, that the sampling distributions, as random variables depending on the random unitaries defining the problem instances, have small second moments.
Wed, 29 May 2019 00:00:00 GMThttp://hdl.handle.net/11420/140732019-05-29T00:00:00ZLieb-Robinson bounds and the simulation of time evolution of local observables in lattice systemshttp://hdl.handle.net/11420/14165Title: Lieb-Robinson bounds and the simulation of time evolution of local observables in lattice systems
Authors: Kliesch, Martin; Gogolin, Christian; Eisert, Jens
Abstract: This is an introductory text reviewing Lieb-Robinson bounds for open and closed quantum many-body systems. We introduce the Heisenberg picture for time-dependent local Liouvillians and state a Lieb-Robinson bound that gives rise to a maximum speed of propagation of correlations in many body systems of locally interacting spins and fermions. Finally, we discuss a number of important consequences concerning the simulation of time evolution and properties of ground states and stationary states.
Wed, 02 Jul 2014 00:00:00 GMThttp://hdl.handle.net/11420/141652014-07-02T00:00:00ZSimultaneous Structures in Convex Signal Recovery—Revisiting the Convex Combination of Normshttp://hdl.handle.net/11420/14085Title: Simultaneous Structures in Convex Signal Recovery—Revisiting the Convex Combination of Norms
Authors: Kliesch, Martin; Szarek, Stanislaw J.; Jung, Peter
Abstract: In compressed sensing one uses known structures of otherwise unknown signals to recover them from as few linear observations as possible. The structure comes in form of some compressibility including different notions of sparsity and low rankness. In many cases convex relaxations allow to efficiently solve the inverse problems using standard convex solvers at almost-optimal sampling rates. A standard practice to account for multiple simultaneous structures in convex optimization is to add further regularizers or constraints. From the compressed sensing perspective there is then the hope to also improve the sampling rate. Unfortunately, when taking simple combinations of regularizers, this seems not to be automatically the case as it has been shown for several examples in recent works. Here, we give an overview over ideas of combining multiple structures in convex programs by taking weighted sums and weighted maximums. We discuss explicitly cases where optimal weights are used reflecting an optimal tuning of the reconstruction. In particular, we extend known lower bounds on the number of required measurements to the optimally weighted maximum by using geometric arguments. As examples, we discuss simultaneously low rank and sparse matrices and notions of matrix norms (in the “square deal” sense) for regularizing for tensor products. We state an SDP formulation for numerically estimating the statistical dimensions and find a tensor case where the lower bound is roughly met up to a factor of two.
Tue, 28 May 2019 00:00:00 GMThttp://hdl.handle.net/11420/140852019-05-28T00:00:00ZReliable Recovery of Hierarchically Sparse Signals for Gaussian and Kronecker Product Measurementshttp://hdl.handle.net/11420/14083Title: Reliable Recovery of Hierarchically Sparse Signals for Gaussian and Kronecker Product Measurements
Authors: Roth, Ingo; Kliesch, Martin; Flinth, Axel; Wunder, Gerhard; Eisert, Jens
Abstract: 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.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/140832020-01-01T00:00:00ZRecovering Quantum Gates from Few Average Gate Fidelitieshttp://hdl.handle.net/11420/14087Title: Recovering Quantum Gates from Few Average Gate Fidelities
Authors: Roth, Ingo; Kueng, Richard; Kimmel, S.; Liu, Y. K.; Gross, David; Eisert, Jens; Kliesch, Martin
Abstract: Characterizing quantum processes is a key task in the development of quantum technologies, especially at the noisy intermediate scale of today's devices. One method for characterizing processes is randomized benchmarking, which is robust against state preparation and measurement errors and can be used to benchmark Clifford gates. Compressed sensing techniques achieve full tomography of quantum channels essentially at optimal resource efficiency. In this Letter, we show that the favorable features of both approaches can be combined. For characterizing multiqubit unitary gates, we provide a rigorously guaranteed and practical reconstruction method that works with an essentially optimal number of average gate fidelities measured with 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 characterizing the coherence of a process.
Wed, 24 Oct 2018 00:00:00 GMThttp://hdl.handle.net/11420/140872018-10-24T00:00:00ZComments on "Improving Compressed Sensing With the Diamond Norm"-Saturation of the Norm Inequalities Between Diamond and Nuclear Normhttp://hdl.handle.net/11420/14086Title: Comments on "Improving Compressed Sensing With the Diamond Norm"-Saturation of the Norm Inequalities Between Diamond and Nuclear Norm
Authors: Michel, Ulrich; Kliesch, Martin; Kueng, Richard; Gross, David
Abstract: The diamond norm plays an important role in quantum information and operator theory. Recently, it has also been proposed as a regularizer for low-rank matrix recovery. The norm constants that bound the diamond norm in terms of the nuclear norm (also known as trace norm) are explicitly known. This paper provides a simple characterization of all operators saturating the upper and lower bounds.
Thu, 01 Nov 2018 00:00:00 GMThttp://hdl.handle.net/11420/140862018-11-01T00:00:00ZProperties of Thermal Quantum States: Locality of Temperature, Decay of Correlations, and Morehttp://hdl.handle.net/11420/14091Title: Properties of Thermal Quantum States: Locality of Temperature, Decay of Correlations, and More
Authors: Kliesch, Martin; Riera, Arnau
Abstract: We review several properties of thermal states of spin Hamiltonians with short range interactions. In particular, we focus on those aspects in which the application of tools coming from quantum information theory has been specially successful in the recent years. This comprises the study of the correlations at finite and zero temperature, the stability against distant and/or weak perturbations, the locality of temperature and their classical simulatability. For the case of states with a finite correlation length, we review the results on their energy distribution and the equivalence of the canonical and microcanonical ensemble.
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/11420/140912018-01-01T00:00:00ZOn the distribution of a product of N Gaussian random variableshttp://hdl.handle.net/11420/14107Title: On the distribution of a product of N Gaussian random variables
Authors: Stojanac, Åeljka; Suess, Daniel; Kliesch, Martin
Abstract: The product of Gaussian random variables appears naturally in many applications in probability theory and statistics. It has been known that the distribution of a product of N such variables can be expressed in terms of a Meijer G-function. Here, we compute a similar representation for the corresponding cumulative distribution function (CDF) and provide a power-log series expansion of the CDF based on the theory of the more general Fox H-functions. Numerical computations show that for small values of the argument the CDF of products of Gaussians is well approximated by the lowest orders of this expansion. Analogous results are also shown for the absolute value as well as the square of such products of N Gaussian random variables. For the latter two settings, we also compute the moment generating functions in terms of Meijer G-functions.
Tue, 01 Aug 2017 00:00:00 GMThttp://hdl.handle.net/11420/141072017-08-01T00:00:00ZQuasilocality and efficient simulation of Markovian quantum dynamicshttp://hdl.handle.net/11420/14113Title: Quasilocality and efficient simulation of Markovian quantum dynamics
Authors: Barthel, Thomas; Kliesch, Martin
Abstract: We consider open many-body systems governed by a time-dependent quantum master equation with short-range interactions. With a generalized Lieb-Robinson bound, we show that the evolution in this very generic framework is quasilocal; i.e., the evolution of observables can be approximated by implementing the dynamics only in a vicinity of the observables' support. The precision increases exponentially with the diameter of the considered subsystem. Hence, time evolution can be simulated on classical computers with a cost that is independent of the system size. Providing error bounds for Trotter decompositions, we conclude that the simulation on a quantum computer is additionally efficient in time. For experiments and simulations in the Schrödinger picture, our result can be used to rigorously bound finite-size effects.
Tue, 05 Jun 2012 00:00:00 GMThttp://hdl.handle.net/11420/141132012-06-05T00:00:00ZReal-space renormalization yields finite correlationshttp://hdl.handle.net/11420/14115Title: Real-space renormalization yields finite correlations
Authors: Barthel, Thomas; Kliesch, Martin; Eisert, Jens
Abstract: Real-space renormalization approaches for quantum lattice systems generate certain hierarchical classes of states that are subsumed by the multiscale entanglement renormalization Ansatz (MERA). It is shown that, with the exception of one spatial dimension, MERA states are actually states with finite correlations, i.e., projected entangled pair states (PEPS) with a bond dimension independent of the system size. Hence, real-space renormalization generates states which can be encoded with local effective degrees of freedom, and MERA states form an efficiently contractible class of PEPS that obey the area law for the entanglement entropy. It is further pointed out that there exist other efficiently contractible schemes violating the area law.
Fri, 02 Jul 2010 00:00:00 GMThttp://hdl.handle.net/11420/141152010-07-02T00:00:00ZFidelity Witnesses for Fermionic Quantum Simulationshttp://hdl.handle.net/11420/14089Title: Fidelity Witnesses for Fermionic Quantum Simulations
Authors: Gluza, M.; Kliesch, Martin; Eisert, Jens; Aolita, Leandro
Abstract: The experimental interest and developments in quantum spin-1/2 chains has increased uninterruptedly over the past decade. In many instances, the target quantum simulation belongs to the broader class of noninteracting fermionic models, constituting an important benchmark. In spite of this class being analytically efficiently tractable, no direct certification tool has yet been reported for it. In fact, in experiments, certification has almost exclusively relied on notions of quantum state tomography scaling very unfavorably with the system size. Here, we develop experimentally friendly fidelity witnesses for all pure fermionic Gaussian target states. Their expectation value yields a tight lower bound to the fidelity and can be measured efficiently. We derive witnesses in full generality in the Majorana-fermion representation and apply them to experimentally relevant spin-1/2 chains. Among others, we show how to efficiently certify strongly out-of-equilibrium dynamics in critical Ising chains. At the heart of the measurement scheme is a variant of importance sampling specially tailored to overlaps between covariance matrices. The method is shown to be robust against finite experimental-state infidelities.
Fri, 11 May 2018 00:00:00 GMThttp://hdl.handle.net/11420/140892018-05-11T00:00:00ZMatrix-product operators and states: NP-hardness and undecidabilityhttp://hdl.handle.net/11420/14111Title: Matrix-product operators and states: NP-hardness and undecidability
Authors: Kliesch, Martin; Gross, Dietmar; Eisert, Jens
Abstract: Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics. This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems. It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues. We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard (nondeterministic-polynomial-time hard) in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.
Thu, 16 Oct 2014 00:00:00 GMThttp://hdl.handle.net/11420/141112014-10-16T00:00:00ZImproving Compressed Sensing with the Diamond Normhttp://hdl.handle.net/11420/14108Title: Improving Compressed Sensing with the Diamond Norm
Authors: Kliesch, Martin; Kueng, Richard; Eisert, Jens; Gross, David
Abstract: In low-rank matrix recovery, one aims to reconstruct a low-rank matrix from a minimal number of linear measurements. Within the paradigm of compressed sensing, this is made computationally efficient by minimizing the nuclear norm as a convex surrogate for rank. In this paper, we identify an improved regularizer based on the so-called diamond norm, a concept imported from quantum information theory. We show that-for a class of matrices saturating a certain norm inequality-the descent cone of the diamond norm is contained in that of the nuclear norm. This suggests superior reconstruction properties for these matrices. We explicitly characterize this set of matrices. Moreover, we demonstrate numerically that the diamond norm indeed outperforms the nuclear norm in a number of relevant applications: These include signal analysis tasks, such as blind matrix deconvolution or the retrieval of certain unitary basis changes, as well as the quantum information problem of process tomography with random measurements. The diamond norm is defined for matrices that can be interpreted as order-4 tensors and it turns out that the above condition depends crucially on that tensorial structure. In this sense, this paper touches on an aspect of the notoriously difficult tensor completion problem.
Thu, 01 Dec 2016 00:00:00 GMThttp://hdl.handle.net/11420/141082016-12-01T00:00:00ZReliable quantum certification of photonic state preparationshttp://hdl.handle.net/11420/14110Title: Reliable quantum certification of photonic state preparations
Authors: Aolita, Leandro; Gogolin, Christian; Kliesch, Martin; Eisert, Jens
Abstract: Quantum technologies promise a variety of exciting applications. Even though impressive progress has been achieved recently, a major bottleneck currently is the lack of practical certification techniques. The challenge consists of ensuring that classically intractable quantum devices perform as expected. Here we present an experimentally friendly and reliable certification tool for photonic quantum technologies: an efficient certification test for experimental preparations of multimode pure Gaussian states, pure non-Gaussian states generated by linear-optical circuits with Fock-basis states of constant boson number as inputs, and pure states generated from the latter class by post-selecting with Fock-basis measurements on ancillary modes. Only classical computing capabilities and homodyne or hetorodyne detection are required. Minimal assumptions are made on the noise or experimental capabilities of the preparation. The method constitutes a step forward in many-body quantum certification, which is ultimately about testing quantum mechanics at large scales.
Wed, 18 Nov 2015 00:00:00 GMThttp://hdl.handle.net/11420/141102015-11-18T00:00:00ZDirect certification of a class of quantum simulationshttp://hdl.handle.net/11420/14104Title: Direct certification of a class of quantum simulations
Authors: Hangleiter, Dominik; Kliesch, Martin; Schwarz, Matthias; Eisert, Jens
Abstract: One of the main challenges in the field of quantum simulation and computation is to identify ways to certify the correct functioning of a device when a classical efficient simulation is not available. Important cases are situations in which one cannot classically calculate local expectation values of state preparations efficiently. In this work, we develop weak-membership formulations of the certification of ground state preparations. We provide a non-interactive protocol for certifying ground states of frustration-free Hamiltonians based on simple energy measurements of local Hamiltonian terms. This certification protocol can be applied to classically intractable analog quantum simulations: For example, using Feynman-Kitaev Hamiltonians, one can encode universal quantum computation in such ground states. Moreover, our certification protocol is applicable to ground state encodings of IQP circuits aiming at the demonstration of quantum supremacy. These can be certified efficiently when the error is polynomially bounded.
Wed, 01 Mar 2017 00:00:00 GMThttp://hdl.handle.net/11420/141042017-03-01T00:00:00ZLocality of Temperaturehttp://hdl.handle.net/11420/14112Title: Locality of Temperature
Authors: Kliesch, Martin; Gogolin, Christian; Kastoryano, M. J.; Riera, Arnau; Eisert, Jens
Abstract: This work is concerned with thermal quantum states of Hamiltonians on spin- and fermionic-lattice systems with short-range interactions. We provide results leading to a local definition of temperature, thereby extending the notion of "intensivity of temperature" to interacting quantum models. More precisely, we derive a perturbation formula for thermal states. The influence of the perturbation is exactly given in terms of a generalized covariance. For this covariance, we prove exponential clustering of correlations above a universal critical temperature that upper bounds physical critical temperatures such as the Curie temperature. As a corollary, we obtain that above the critical temperature, thermal states are stable against distant Hamiltonian perturbations. Moreover, our results imply that above the critical temperature, local expectation values can be approximated efficiently in the error and the system size.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11420/141122014-01-01T00:00:00ZDissipative quantum Church-Turing theoremhttp://hdl.handle.net/11420/14114Title: Dissipative quantum Church-Turing theorem
Authors: Kliesch, Martin; Barthel, Thomas; Gogolin, Christian; Kastoryano, M. J.; Eisert, Jens
Abstract: We show that the time evolution of an open quantum system, described by a possibly time dependent Liouvillian, can be simulated by a unitary quantum circuit of a size scaling polynomially in the simulation time and the size of the system. An immediate consequence is that dissipative quantum computing is no more powerful than the unitary circuit model. Our result can be seen as a dissipative Church-Turing theorem, since it implies that under natural assumptions, such as weak coupling to an environment, the dynamics of an open quantum system can be simulated efficiently on a quantum computer. Formally, we introduce a Trotter decomposition for Liouvillian dynamics and give explicit error bounds. This constitutes a practical tool for numerical simulations, e.g., using matrix-product operators. We also demonstrate that most quantum states cannot be prepared efficiently.
Mon, 12 Sep 2011 00:00:00 GMThttp://hdl.handle.net/11420/141142011-09-12T00:00:00ZClosed-form analytic expressions for shadow estimation with brickwork circuitshttp://hdl.handle.net/11420/14132Title: Closed-form analytic expressions for shadow estimation with brickwork circuits
Authors: Arienzo, Mirko; Heinrich, Markus; Roth, Ingo; Kliesch, Martin
Abstract: 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.
Tue, 01 Nov 2022 00:00:00 GMThttp://hdl.handle.net/11420/141322022-11-01T00:00:00ZLearning logical quantum noise in quantum error correctionhttp://hdl.handle.net/11420/14134Title: Learning logical quantum noise in quantum error correction
Authors: Wagner, Thomas; Kampermann, Hermann; Bruß, Dagmar; Kliesch, Martin
Abstract: The characterization of quantum devices is crucial for their practical implementation but can be costly in experimental effort and classical post-processing. Therefore, it is desirable to measure only the information that is relevant for specific applications and develop protocols that require little additional effort. In this work, we focus on the characterization of quantum computers in the context of stabilizer quantum error correction. Our main result is that the logical error channel induced by Pauli noise can be estimated from syndrome data under minimal conditions. More precisely, we show that the estimation is possible as long as the code can correct the noise.
Mon, 19 Sep 2022 00:00:00 GMThttp://hdl.handle.net/11420/141342022-09-19T00:00:00ZPauli channels can be estimated from syndrome measurements in quantum error correctionhttp://hdl.handle.net/11420/14074Title: Pauli channels can be estimated from syndrome measurements in quantum error correction
Authors: Wagner, Thomas; Kampermann, Hermann; Bruß, Dagmar; Kliesch, Martin
Abstract: The performance of quantum error correction can be significantly improved if detailed information about the noise is available, allowing to optimize both codes and decoders. It has been proposed to estimate error rates from the syndrome measurements done anyway during quantum error correction. While these measurements preserve the encoded quantum state, it is currently not clear how much information about the noise can be extracted in this way. So far, apart from the limit of vanishing error rates, rigorous results have only been established for some specific codes. In this work, we rigorously resolve the question for arbitrary stabilizer codes. The main result is that a stabilizer code can be used to estimate Pauli channels with correlations across a number of qubits given by the pure distance. This result does not rely on the limit of vanishing error rates, and applies even if high weight errors occur frequently. Moreover, it also allows for measurement errors within the framework of quantum data-syndrome codes. Our proof combines Boolean Fourier analysis, combinatorics and elementary algebraic geometry. It is our hope that this work opens up interesting applications, such as the online adaptation of a decoder to time-varying noise.
Sat, 01 Jan 2022 00:00:00 GMThttp://hdl.handle.net/11420/140742022-01-01T00:00:00ZFast gradient estimation for variational quantum algorithmshttp://hdl.handle.net/11420/14133Title: Fast gradient estimation for variational quantum algorithms
Authors: Bittel, Lennart; Watty, Jens; Kliesch, Martin
Abstract: Many optimization methods for training variational quantum algorithms are based on estimating gradients of the cost function. Due to the statistical nature of quantum measurements, this estimation requires many circuit evaluations, which is a crucial bottleneck of the whole approach. We propose a new gradient estimation method to mitigate this measurement challenge and reduce the required measurement rounds. Within a Bayesian framework and based on the generalized parameter shift rule, we use prior information about the circuit to find an estimation strategy that minimizes expected statistical and systematic errors simultaneously. We demonstrate that this approach can significantly outperform traditional gradient estimation methods, reducing the required measurement rounds by up to an order of magnitude for a common QAOA setup. Our analysis also shows that an estimation via finite differences can outperform the parameter shift rule in terms of gradient accuracy for small and moderate measurement budgets.
Wed, 12 Oct 2022 00:00:00 GMThttp://hdl.handle.net/11420/141332022-10-12T00:00:00ZGuaranteed recovery of quantum processes from few measurementshttp://hdl.handle.net/11420/13933Title: Guaranteed recovery of quantum processes from few measurements
Authors: Kliesch, Martin; Kueng, Richard; Eisert, Jens; Gross, David
Abstract: Quantum process tomography is the task of reconstructing unknown quantum channels from measured data. In this work, we introduce compressed sensing-based methods that facilitate the reconstruction of quantum channels of low Kraus rank. Our main contribution is the analysis of a natural measurement model for this task: We assume that data is obtained by sending pure states into the channel and measuring expectation values on the output. Neither ancillary systems nor coherent operations across multiple channel uses are required. Most previous results on compressed process reconstruction reduce the problem to quantum state tomography on the channel's Choi matrix. While this ansatz yields recovery guarantees from an essentially minimal number of measurements, physical implementations of such schemes would typically involve ancillary systems. A priori, it is unclear whether a measurement model tailored directly to quantum process tomography might require more measurements. We establish that this is not the case. Technically, we prove recovery guarantees for three different reconstruction algorithms. The reconstructions are based on a trace, diamond, and `2-norm minimization, respectively. Our recovery guarantees are uniform in the sense that with one random choice of measurement settings all quantum channels can be recovered equally well. Moreover, stability against arbitrary measurement noise and robustness against violations of the low-rank assumption is guaranteed. Numerical studies demonstrate the feasibility of the approach.
Mon, 12 Aug 2019 00:00:00 GMThttp://hdl.handle.net/11420/139332019-08-12T00:00:00ZSynthesis of and compilation with time-optimal multi-qubit gateshttp://hdl.handle.net/11420/14164Title: Synthesis of and compilation with time-optimal multi-qubit gates
Authors: Baßler, Pascal; Zipper, Matthias; Cedzich, Christopher; Heinrich, Markus; Huber, Patrick; Johanning, Michael; Kliesch, Martin
Abstract: We develop a method to synthesize a class of entangling multi-qubit gates for a quantum computing platform with fixed Ising-type interaction with all-to-all connectivity. The only requirement on the flexibility of the interaction is that it can be switched on and off for individual qubits. Our method yields a time-optimal implementation of the multi-qubit gates. We numerically demonstrate that the total multi-qubit gate time scales approximately linear in the number of qubits. Using this gate synthesis as a subroutine, we provide compilation strategies for important use cases: (i) we show that any Clifford circuit on n qubits can be implemented using at most n multi-qubit gates without requiring ancilla qubits, (ii) we decompose the quantum Fourier transform in a similar fashion, (iii) we compile a simulation of molecular dynamics, and (iv) we propose a method for the compilation of diagonal unitaries with time-optimal multi-qubit gates, as a step towards general unitaries. As motivation, we provide a detailed discussion on a microwave controlled ion trap architecture with magnetic gradient induced coupling (MAGIC) for the generation of the Ising-type interactions.
Mon, 13 Jun 2022 00:00:00 GMThttp://hdl.handle.net/11420/141642022-06-13T00:00:00ZScalable approach to many-body localization via quantum datahttp://hdl.handle.net/11420/14162Title: Scalable approach to many-body localization via quantum data
Authors: Gresch, Alexander; Bittel, Lennart; Kliesch, Martin
Abstract: We are interested in how quantum data can allow for practical solutions to otherwise difficult computational problems. A notoriously difficult phenomenon from quantum many-body physics is the emergence of many-body localization (MBL). So far, is has evaded a comprehensive analysis. In particular, numerical studies are challenged by the exponential growth of the Hilbert space dimension. As many of these studies rely on exact diagonalization of the system's Hamiltonian, only small system sizes are accessible. In this work, we propose a highly flexible neural network based learning approach that, once given training data, circumvents any computationally expensive step. In this way, we can efficiently estimate common indicators of MBL such as the adjacent gap ratio or entropic quantities. Our estimator can be trained on data from various system sizes at once which grants the ability to extrapolate from smaller to larger ones. Moreover, using transfer learning we show that already a two-dimensional feature vector is sufficient to obtain several different indicators at various energy densities at once. We hope that our approach can be applied to large-scale quantum experiments to provide new insights into quantum many-body physics.
Thu, 17 Feb 2022 00:00:00 GMThttp://hdl.handle.net/11420/141622022-02-17T00:00:00ZCompressive gate set tomographyhttp://hdl.handle.net/11420/14161Title: Compressive gate set tomography
Authors: Brieger, Raphael; Roth, Ingo; Kliesch, Martin
Abstract: 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.
Thu, 09 Dec 2021 00:00:00 GMThttp://hdl.handle.net/11420/141612021-12-09T00:00:00ZBoson-Sampling in the light of sample complexityhttp://hdl.handle.net/11420/14166Title: Boson-Sampling in the light of sample complexity
Authors: Gogolin, Christian; Kliesch, Martin; Aolita, Leandro; Eisert, Jens
Abstract: Boson-Sampling is a classically computationally hard problem that can - in principle - be efficiently solved with quantum linear optical networks. Very recently, a rush of experimental activity has ignited with the aim of developing such devices as feasible instances of quantum simulators. Even approximate Boson-Sampling is believed to be hard with high probability if the unitary describing the optical network is drawn from the Haar measure. In this work we show that in this setup, with probability exponentially close to one in the number of bosons, no symmetric algorithm can distinguish the Boson-Sampling distribution from the uniform one from fewer than exponentially many samples. This means that the two distributions are operationally indistinguishable without detailed a priori knowledge. We carefully discuss the prospects of efficiently using knowledge about the implemented unitary for devising non-symmetric algorithms that could potentially improve upon this. We conclude that due to the very fact that Boson-Sampling is believed to be hard, efficient classical certification of Boson-Sampling devices seems to be out of reach.
Mon, 17 Jun 2013 00:00:00 GMThttp://hdl.handle.net/11420/141662013-06-17T00:00:00ZGuaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGroupinghttp://hdl.handle.net/11420/14532Title: Guaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGrouping
Authors: Gresch, Alexander; Kliesch, Martin
Abstract: Energy estimation in quantum many-body Hamiltonians is a paradigmatic task in various research fields. In particular, efficient energy estimation may be crucial in achieving a quantum advantage for a practically relevant problem. For instance, the measurement effort poses a crucial bottleneck in variational quantum algorithms. We aim to find the optimal strategy with single-qubit measurements that yields the highest provable accuracy given a total measurement budget. As a central tool, we establish new tail bounds for empirical estimators of the energy. They are useful for identifying measurement settings that improve the energy estimate the most. This task constitutes an NP-hard problem. However, we are able to circumvent this bottleneck and use the tail bounds to develop a practical efficient estimation strategy which we call ShadowGrouping. As the name suggests, it combines shadow estimation methods with grouping strategies for Pauli strings. In numerical experiments, we demonstrate that ShadowGrouping outperforms state-of-the-art methods in estimating the electronic ground-state energies of various small molecules, both in provable and effective accuracy benchmarks. Hence, this work provides a promising way, e.g., to tackle the measurement bottleneck of variational quantum algorithms.
Mon, 09 Jan 2023 00:00:00 GMThttp://hdl.handle.net/11420/145322023-01-09T00:00:00ZDistance-based resource quantification for sets of quantum measurementshttp://hdl.handle.net/11420/14163Title: Distance-based resource quantification for sets of quantum measurements
Authors: Tendick, Lucas; Kliesch, Martin; Kampermann, Hermann; Bruß, Dagmar
Abstract: The advantage that quantum systems provide for certain quantum information processing tasks over their classical counterparts can be quantified within the general framework of resource theories. Certain distance functions between quantum states have successfully been used to quantify resources like entanglement and coherence. Perhaps surprisingly, such a distance-based approach has not been adopted to study resources of quantum measurements, where other geometric quantifiers are used instead. Here, we define distance functions between sets of quantum measurements and show that they naturally induce resource monotones for convex resource theories of measurements. By focusing on a distance based on the diamond norm, we establish a hierarchy of measurement resources and derive analytical bounds on the incompatibility of any set of measurements. We show that these bounds are tight for certain projective measurements based on mutually unbiased bases and identify scenarios where different measurement resources attain the same value when quantified by our resource monotone. Our results provide a general framework to compare distance-based resources for sets of measurements and allow us to obtain limitations on Bell-type experiments.
Tue, 17 May 2022 00:00:00 GMThttp://hdl.handle.net/11420/141632022-05-17T00:00:00ZMixing Properties of Stochastic Quantum Hamiltonianshttp://hdl.handle.net/11420/14092Title: Mixing Properties of Stochastic Quantum Hamiltonians
Authors: Onorati, E.; Buerschaper, O.; Kliesch, Martin; Brown, W.; Werner, Albert H.; Eisert, Jens
Abstract: Random quantum processes play a central role both in the study of fundamental mixing processes in quantum mechanics related to equilibration, thermalisation and fast scrambling by black holes, as well as in quantum process design and quantum information theory. In this work, we present a framework describing the mixing properties of continuous-time unitary evolutions originating from local Hamiltonians having time-fluctuating terms, reflecting a Brownian motion on the unitary group. The induced stochastic time evolution is shown to converge to a unitary design. As a first main result, we present bounds to the mixing time. By developing tools in representation theory, we analytically derive an expression for a local k-th moment operator that is entirely independent of k, giving rise to approximate unitary k-designs and quantum tensor product expanders. As a second main result, we introduce tools for proving bounds on the rate of decoupling from an environment with random quantum processes. By tying the mathematical description closely with the more established one of random quantum circuits, we present a unified picture for analysing local random quantum and classes of Markovian dissipative processes, for which we also discuss applications.
Wed, 01 Nov 2017 00:00:00 GMThttp://hdl.handle.net/11420/140922017-11-01T00:00:00ZPositive Tensor Network Approach for Simulating Open Quantum Many-Body Systemshttp://hdl.handle.net/11420/14109Title: Positive Tensor Network Approach for Simulating Open Quantum Many-Body Systems
Authors: Werner, Albert H.; Jaschke, Daniel; Silvi, P.; Kliesch, Martin; Calarco, T.; Eisert, Jens; Montangero, S.
Abstract: Open quantum many-body systems play an important role in quantum optics and condensed matter physics, and capture phenomena like transport, the interplay between Hamiltonian and incoherent dynamics, and topological order generated by dissipation. We introduce a versatile and practical method to numerically simulate one-dimensional open quantum many-body dynamics using tensor networks. It is based on representing mixed quantum states in a locally purified form, which guarantees that positivity is preserved at all times. Moreover, the approximation error is controlled with respect to the trace norm. Hence, this scheme overcomes various obstacles of the known numerical open-system evolution schemes. To exemplify the functioning of the approach, we study both stationary states and transient dissipative behavior, for various open quantum systems ranging from few to many bodies.
Tue, 07 Jun 2016 00:00:00 GMThttp://hdl.handle.net/11420/141092016-06-07T00:00:00ZOptimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximatehttp://hdl.handle.net/11420/14490Title: Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate
Authors: Bittel, Lennart; Gharibian, Sevag; Kliesch, Martin
Abstract: Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the depth of the variational ansatz used - the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. This potential for depth reduction has made VQAs a staple of Noisy Intermediate-Scale Quantum (NISQ)-era research.
In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that for any constant ϵ>0, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor N¹⁻ϵ, for N denoting the encoding size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP.) We then show that this hardness persists even in the "simpler" setting of QAOAs. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems. To achieve these results, we bypass the need for a PCP theorem for QCMA by appealing to the disperser-based NP-hardness of approximation construction of [Umans, FOCS 1999].
Tue, 22 Nov 2022 00:00:00 GMThttp://hdl.handle.net/11420/144902022-11-22T00:00:00ZGeneral guarantees for randomized benchmarking with random quantum circuitshttp://hdl.handle.net/11420/14489Title: General guarantees for randomized benchmarking with random quantum circuits
Authors: Heinrich, Markus; Kliesch, Martin; Roth, Ingo
Abstract: 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 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.
Mon, 12 Dec 2022 00:00:00 GMThttp://hdl.handle.net/11420/144892022-12-12T00:00:00Z