Search

Information inequalities govern the ultimate limitations in information theory and as such play an pivotal role in characterizing what values the entropy of multipartite states can take. Proving an information inequality, however, quickly becomes arduous when the number of involved parties increases. For classical systems, [Yeung, IEEE Trans. Inf. Theory (1997)] proposed a framework to prove Shannon-type inequalities via linear programming. Here, we derive an analogous framework for quantum systems, based on the strong sub-additivity and weak monotonicity inequalities for the von-Neumann entropy. Importantly, this also allows us to handle constrained inequalities, which - in the classical case - served as a crucial tool in proving the existence of non-standard, so-called non-Shannon-type inequalities [Zhang & Yeung, IEEE Trans. Inf. Theory (1998)]. Our main contribution is the Python package qITIP, for which we present the theory and demonstrate its capabilities with several illustrative examples, Comment: Submitted to conference 2025 IEEE International Symposium on Information Theory; 5 pages + 1 page references

Recently, there have been several advancements in quantum algorithms for Gibbs sampling. These algorithms simulate the dynamics generated by an artificial Lindbladian, which is meticulously constructed to obey a detailed-balance condition with the Gibbs state of interest, ensuring it is a stationary point of the evolution, while simultaneously having efficiently implementable time steps. The overall complexity then depends primarily on the mixing time of the Lindbladian, which can vary drastically, but which has been previously bounded in the regime of high enough temperatures [Rouz\'e {\it et al.}~arXiv:2403.12691 and arXiv:2411.04885]. In this work, we calculate the spectral gap of the Lindbladian for free fermions using third quantisation, and then prove a constant gap of the perturbed Lindbladian corresponding to interacting fermions up to some maximal coupling strength. This is achieved by using theorems about stability of the gap for lattice fermions. Our methods apply at any constant temperature and independently of the system size. The gap then provides an upper bound on the mixing time, and hence on the overall complexity of the quantum algorithm, proving that the purified Gibbs state of weakly interacting (quasi-)local fermionic systems of any dimension can be prepared in $\widetilde{\mathcal{O}} (n^3 \operatorname{polylog}(1/\epsilon))$ time on $\mathcal{O}(n)$ qubits, where $n$ denotes the size of the system and $\epsilon$ the desired accuracy. We provide exact numerical simulations for small system sizes supporting the theory and also identify different suitable jump operators and filter functions for the sought-after regime of intermediate coupling in the Fermi-Hubbard model.

We study relaxations of entanglement-assisted quantum channel coding and establish that non-signaling assistance and the meta-converse are equivalent in terms of success probabilities. We then present a rounding procedure that transforms any non-signaling-assisted strategy into an entanglement-assisted one and prove an approximation ratio of $(1 - e^{-1})$ in success probabilities for the special case of measurement channels. For fully quantum channels, we give a weaker (dimension dependent) approximation ratio, that is nevertheless still tight to characterize the strong converse exponent of entanglement-assisted channel coding [Li and Yao, arXiv:2209.00555]. Our derivations leverage ideas from position-based decoding, quantum decoupling theorems, the matrix Chernoff inequality, and input flattening techniques., Comment: 27+4 pages, 1 Figure

We consider the problem of shared randomness-assisted multiple access channel (MAC) simulation for product inputs and characterize the one-shot communication cost region via almost-matching inner and outer bounds in terms of the smooth max-information of the channel, featuring auxiliary random variables of bounded size. The achievability relies on a rejection-sampling algorithm to simulate an auxiliary channel between each sender and the decoder, and producing the final output based on the output of these intermediate channels. The converse follows via information-spectrum based arguments. To bound the cardinality of the auxiliary random variables, we employ the perturbation method from [Anantharam et al., IEEE Trans. Inf. Theory (2019)] in the one-shot setting. For the asymptotic setting and vanishing errors, our result expands to a tight single-letter rate characterization and consequently extends a special case of the simulation results of [Kurri et al., IEEE Trans. Inf. Theory (2022)] for fixed, independent and identically distributed (iid) product inputs to universal simulation for any product inputs. We broaden our discussion into the quantum realm by studying feedback simulation of quantum-to-classical (QC) MACs with product measurements [Atif et al., IEEE Trans. Inf. Theory (2022)]. For fixed product inputs and with shared randomness assistance, we give a quasi tight one-shot communication cost region with corresponding single-letter asymptotic iid expansion., Comment: Total 42 pages, main text 23 pages, References and Appendices 19 pages, 2 Figures

We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexity of two primitive problems: given a function $f$ and a Hermitian matrix $A$, compute a matrix element of $f(A)$ or compute a local measurement on $f(A)|0\rangle^{\otimes n}$, with $|0\rangle^{\otimes n}$ an $n$-qubit reference state vector, in both cases up to additive approximation error. We consider four functions -- monomials, Chebyshev polynomials, the time evolution function, and the inverse function -- and probe the complexity across a broad landscape covering different problem input regimes. Namely, we consider two types of matrix inputs (sparse and Pauli access), matrix properties (norm, sparsity), the approximation error, and function-specific parameters. We identify BQP-complete forms of both problems for each function and then toggle the problem parameters to easier regimes to see where hardness remains, or where the problem becomes classically easy. As part of our results we make concrete a hierarchy of hardness across the functions; in parameter regimes where we have classically efficient algorithms for monomials, all three other functions remain robustly BQP-hard, or hard under usual computational complexity assumptions. In identifying classically easy regimes, among others, we show that for any polynomial of degree $\mathrm{poly}(n)$ both problems can be efficiently classically simulated when $A$ has $O(\log n)$ non-zero coefficients in the Pauli basis. This contrasts with the fact that the problems are BQP-complete in the sparse access model even for constant row sparsity, whereas the stated Pauli access efficiently constructs sparse access with row sparsity $O(\log n)$. Our work provides a catalog of efficient quantum and classical algorithms for fundamental linear-algebra tasks., Comment: 11+28 pages, 1 table, 2 figures

The quantum dichotomies problem asks at what rate one pair of quantum states can be approximately mapped into another pair of quantum states. In the many copy limit and for vanishing error, the optimal rate is known to be given by the ratio of the respective quantum relative distances. Here, we study the large-deviation behavior of quantum dichotomies and determine the exact strong converse exponent based on the purified distance. Our result is characterized by a simple optimization of quantum R\'enyi information measures involving all four mutually non-commuting quantum states. Our findings thus constitute an operational example of studying multivariate extensions of quantum R\'enyi information measure., Comment: 12+3 pages

We determine the exact error and strong converse exponent for entanglement-assisted classical-quantum channel simulation in worst case input purified distance. The error exponent is expressed as a single-letter formula optimized over sandwiched R\'enyi divergences of order $\alpha \in [1, \infty)$, notably without the need for a critical rate--a sharp contrast to the error exponent for classical-quantum channel coding. The strong converse exponent is expressed as a single-letter formula optimized over sandwiched R\'enyi divergences of order $\alpha\in [\frac{1}{2},1]$. As in the classical work [Oufkir et al., arXiv:2410.07051], we start with the goal of asymptotically expanding the meta-converse for channel simulation in the relevant regimes. However, to deal with non-commutativity issues arising from classical-quantum channels and entanglement-assistance, we critically use various properties of the quantum fidelity, additional auxiliary channel techniques, approximations via Chebyshev inequalities, and entropic continuity bounds., Comment: 27+5 pages

The trade-offs between error probabilities in quantum hypothesis testing are by now well-understood in the centralized setting, but much less is known for distributed settings. Here, we study a distributed binary hypothesis testing problem to infer a bipartite quantum state shared between two remote parties, where one of these parties communicates to the tester at zero-rate, while the other party communicates to the tester at zero-rate or higher. As our main contribution, we derive an efficiently computable single-letter formula for the Stein's exponent of this problem, when the state under the alternative is product. For the general case, we show that the Stein's exponent when (at least) one of the parties communicates classically at zero-rate is given by a multi-letter expression involving max-min optimization of regularized measured relative entropy. While this becomes single-letter for the fully classical case, we further prove that this already does not happen in the same way for classical-quantum states in general. As a key tool for proving the converse direction of our results, we develop a quantum version of the blowing-up lemma which may be of independent interest., Comment: 34+2 pages; Added single-letter characterization of Stein's exponent under zero-rate (fully) quantum communication when state under alternative is product

We study the effect of shared non-signaling correlations for the problem of simulating a channel using noiseless communication in the one-shot setting. For classical channels, we show how to round any non-signaling-assisted simulation strategy--which corresponds to the natural linear programming meta-converse for channel simulation--to a strategy that only uses shared randomness. For quantum channels, we round any non-signaling-assisted simulation strategy to a strategy that only uses shared entanglement. Our main result is for classical and classical-quantum channels, for which we employ ideas from approximation algorithms to give a guarantee on the ratio of success probabilities of at least $(1-\mathrm{e}^{-1})$. We further show this ratio to be optimal for the purely classical case. It can be improved to $(1-t^{-1})$ using $O(\ln \ln(t))$ additional bits of communication., Comment: 23+6 pages

We determine the exact error and strong converse exponents of shared randomness-assisted channel simulation in worst case total-variation distance. Namely, we find that these exponents can be written as simple optimizations over the R\'enyi channel mutual information. Strikingly, and in stark contrast to channel coding, there are no critical rates, allowing a tight characterization for arbitrary rates below and above the simulation capacity. We derive our results by asymptotically expanding the meta-converse for channel simulation [Cao {\it et al.}, IEEE Trans.~Inf.~Theory (2024)], which corresponds to non-signaling assisted codes. We prove this to be asymptotically tight by employing the approximation algorithms from [Berta {\it et al.}, Proc.~IEEE ISIT (2024)], which show how to round any non-signaling assisted strategy to a strategy that only uses shared randomness. Notably, this implies that any additional quantum entanglement-assistance does not change the error or the strong converse exponents., Comment: 27+6 pages

We provide a tight asymptotic characterization of the error exponent for classical-quantum channel coding assisted by activated non-signaling correlations. Namely, we find that the optimal exponent--also called reliability function--is equal to the well-known sphere packing bound, which can be written as a single-letter formula optimized over Petz-R\'enyi divergences. Remarkably, there is no critical rate and as such our characterization remains tight for arbitrarily low rates below the capacity. On the achievability side, we further extend our results to fully quantum channels. Our proofs rely on semi-definite program duality and a dual representation of the Petz-R\'enyi divergences via Young inequalities., Comment: 20+10 pages. v2: updated references to arXiv:1609.08462 and arXiv:1710.10252 about reversed Petz sandwiched inequalities

We show that Frenkel's integral representation of the quantum relative entropy provides a natural framework to derive continuity bounds for quantum information measures. Our main general result is a dimension-independent semi-continuity relation for the quantum relative entropy with respect to the first argument. Using it, we obtain a number of results: (1) a tight continuity relation for the conditional entropy in the case where the two states have equal marginals on the conditioning system, resolving a conjecture by Wilde in this special case; (2) a stronger version of the Fannes-Audenaert inequality on quantum entropy; (3) better estimates on the quantum capacity of approximately degradable channels; (4) an improved continuity relation for the entanglement cost; (5) general upper bounds on asymptotic transformation rates in infinite-dimensional entanglement theory; and (6) a proof of a conjecture due to Christandl, Ferrara, and Lancien on the continuity of 'filtered' relative entropy distances., Comment: 23 pages. In v2 we removed the claims on continuity of quantum channel capacities, as tighter bounds due to Shirokov are already available

Despite the central importance of quantum entanglement in fueling many quantum technologies, the understanding of the optimal ways to exploit it is still beyond our reach, and even measuring entanglement in an operationally meaningful way is prohibitively difficult. This is due to the need to precisely characterise many-copy, asymptotic protocols for entanglement processing. Here we overcome these issues by introducing a new way of benchmarking the fundamental protocol of entanglement distillation (purification), where instead of measuring its asymptotic yield, we focus on the best achievable error. We connect this formulation of the task with an information-theoretic problem in composite quantum hypothesis testing known as generalised Sanov's theorem. By solving the latter problem -- which had no previously known solution even in classical information theory -- we thus compute the optimal asymptotic error exponent of entanglement distillation. We show this asymptotic solution to be given by the reverse relative entropy of entanglement, a single-letter quantity that can be evaluated using only a single copy of a quantum state, which is a unique feature among operational measures of entanglement. Altogether, we thus demonstrate a measure of entanglement that admits a direct operational interpretation as the optimal asymptotic rate of an important entanglement manipulation protocol while enjoying an exact, single-letter formula., Comment: 18+18 pages

We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. The functional form of these response functions can be mapped to a corresponding eigenproblem of a Hermitian matrix $H$, thus suggesting the use of quantum phase estimation. Our proposed quantum algorithm operates in the standard $s$-sparse, oracle-based query access model. For a network of $N$ oscillators with maximum norm $\lVert H \rVert_{\mathrm{max}}$, and when the eigenvalue tolerance $\varepsilon$ is much smaller than the minimum eigenvalue gap, we use $\mathcal{O}(\log(N s \lVert H \rVert_{\mathrm{max}}/\varepsilon)$ algorithmic qubits and obtain a rigorous worst-case query complexity upper bound $\mathcal{O}(s \lVert H \rVert_{\mathrm{max}}/(\delta^2 \varepsilon) )$ up to logarithmic factors, where $\delta$ denotes the desired precision on the coefficients appearing in the response functions. Crucially, our proposal does not suffer from the infamous state preparation bottleneck and can as such potentially achieve large quantum speedups compared to relevant classical methods. As a proof-of-principle of exponential quantum speedup, we show that a simple adaptation of our algorithm solves the random glued-trees problem in polynomial time. We discuss practical limitations as well as potential improvements for quantifying finite size, end-to-end complexities for application to relevant instances., Comment: 13+9 pages, 8 figures

We propose an extension of the classical R\'enyi divergences to quantum states through an optimization over probability distributions induced by restricted sets of measurements. In particular, we define the notion of locally-measured R\'enyi divergences, where the set of allowed measurements originates from variants of locality constraints between (distant) parties $A$ and $B$. We then derive variational bounds on the locally-measured R\'enyi divergences and systematically discuss when these bounds become exact characterizations. As an application, we evaluate the locally-measured R\'enyi divergences on variants of highly symmetric data-hiding states, showcasing the reduced distinguishing power of locality-constrained measurements. For $n$-fold tensor powers, we further employ our variational formulae to derive corresponding additivity results, which gives the locally-measured R\'enyi divergences operational meaning as optimal rate exponents in asymptotic locally-measured hypothesis testing., Comment: 35+11 pages

Estimation of quantum relative entropy and its R\'{e}nyi generalizations is a fundamental statistical task in quantum information theory, physics, and beyond. While several estimators of these divergences have been proposed in the literature along with their computational complexities explored, a limit distribution theory which characterizes the asymptotic fluctuations of the estimation error is still premature. As our main contribution, we characterize these asymptotic distributions in terms of Fr\'{e}chet derivatives of elementary operator-valued functions. We achieve this by leveraging an operator version of Taylor's theorem and identifying the regularity conditions needed. As an application of our results, we consider an estimator of quantum relative entropy based on Pauli tomography of quantum states and show that the resulting asymptotic distribution is a centered normal, with its variance characterized in terms of the Pauli operators and states. We utilize the knowledge of the aforementioned limit distribution to obtain asymptotic performance guarantees for a multi-hypothesis testing problem., Comment: 14+30 pages

The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered., Comment: Survey document with wiki-like modular structure. 337 pages, including bibliography and sub-bibliographies. Comments welcome

Entropy is a fundamental concept in quantum information theory that allows to quantify entanglement and investigate its properties, for example its monogamy over multipartite systems. Here, we derive variational formulas for relative entropies based on restricted measurements of multipartite quantum systems. By combining these with multivariate matrix trace inequalities, we recover and sometimes strengthen various existing entanglement monogamy inequalities. In particular, we give direct, matrix-analysis-based proofs for the faithfulness of squashed entanglement by relating it to the relative entropy of entanglement measured with one-way local operations and classical communication, as well as for the faithfulness of conditional entanglement of mutual information by relating it to the separably measured relative entropy of entanglement. We discuss variations of these results using the relative entropy to states with positive partial transpose, and multipartite setups. Our results simplify and generalize previous derivations in the literature that employed operational arguments about the asymptotic achievability of information-theoretic tasks., Comment: 22 pages; v2: published version

We show that the communication cost of quantum broadcast channel simulation under free entanglement assistance between the sender and the receivers is asymptotically characterized by an efficiently computable single-letter formula in terms of the channel's multipartite mutual information. Our core contribution is a new one-shot achievability result for multipartite quantum state splitting via multipartite convex splitting. As part of this, we face a general instance of the quantum joint typicality problem with arbitrarily overlapping marginals. The crucial technical ingredient to sidestep this difficulty is a conceptually novel multipartite mean-zero decomposition lemma, together with employing recently introduced complex interpolation techniques for sandwiched R\'enyi divergences. Moreover, we establish an exponential convergence of the simulation error when the communication costs are within the interior of the capacity region. As the costs approach the boundary of the capacity region moderately quickly, we show that the error still vanishes asymptotically., Comment: The idea of the mean-zero decomposition lemma is independently and concurrently discovered for multipartite decoupling by Pau Colomer Saus and Andreas Winter (arXiv:2304.12114). v2: References updated

A new finite form of de Finetti's representation theorem is established using elementary information-theoretic tools. The distribution of the first $k$ random variables in an exchangeable vector of $n\geq k$ random variables is close to a mixture of product distributions. Closeness is measured in terms of the relative entropy and an explicit bound is provided. This bound is tighter than those obtained via earlier information-theoretic proofs, and its utility extends to random variables taking values in general spaces. The core argument employed has its origins in the quantum information-theoretic literature., Comment: 11 pages, no figures. In the second version the introduction is slightly extended, two new references and Section 2.4 have been added

A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. For this task, there is a well-studied quantum algorithm that performs quantum phase estimation on an initial trial state that has a nonnegligible overlap with a low-energy state. However, it is notoriously hard to give theoretical guarantees that such a trial state can be prepared efficiently. Moreover, the heuristic proposals that are currently available, such as with adiabatic state preparation, appear insufficient in practical cases. This paper shows that, for most random sparse Hamiltonians, the maximally mixed state is a sufficiently good trial state, and phase estimation efficiently prepares states with energy arbitrarily close to the ground energy. Furthermore, any low-energy state must have nonnegligible quantum circuit complexity, suggesting that low-energy states are classically nontrivial and phase estimation is the optimal method for preparing such states (up to polynomial factors). These statements hold for two models of random Hamiltonians: (i) a sum of random signed Pauli strings and (ii) a random signed $d$-sparse Hamiltonian. The main technical argument is based on some new results in nonasymptotic random matrix theory. In particular, a refined concentration bound for the spectral density is required to obtain complexity guarantees for these random Hamiltonians., Comment: 33 pages, 4 figures

We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For $N\times N$ Hermitian matrices, the space cost is $\log(N)+1$ qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size $O(N^2)$, when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these sub-routines to present a scheme for calculating Green's functions of quantum many-body systems., Comment: 20+31 pages, 2+1 figures, 4 tables. Updated to published version

We study channel simulation under common randomness assistance in the finite-blocklength regime and identify the smooth channel max-information as a linear program one-shot converse on the minimal simulation cost for fixed error tolerance. We show that this one-shot converse can be achieved exactly using no-signaling-assisted codes, and approximately achieved using common randomness-assisted codes. Our one-shot converse thus takes on an analogous role to the celebrated meta-converse in the complementary problem of channel coding, and we find tight relations between these two bounds. We asymptotically expand our bounds on the simulation cost for discrete memoryless channels, leading to the second-order as well as the moderate deviation rate expansion, which can be expressed in terms of the channel capacity and channel dispersion known from noisy channel coding. Our bounds imply the well-known fact that the optimal asymptotic rate of one channel to simulate another under common randomness assistance is given by the ratio of their respective capacities. Additionally, our higher-order asymptotic expansion shows that this reversibility falls apart in the second order. Our techniques extend to discrete memoryless broadcast channels. In stark contrast to the elusive broadcast channel capacity problem, we show that the reverse problem of broadcast channel simulation under common randomness assistance allows for an efficiently computable single-letter characterization of the asymptotic rate region in terms of the broadcast channel's multipartite mutual information., Comment: 38 pages, 6 figures

We study quantum interior point methods (QIPMs) for second-order cone programming (SOCP), guided by the example use case of portfolio optimization (PO). We provide a complete quantum circuit-level description of the algorithm from problem input to problem output, making several improvements to the implementation of the QIPM. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm, including constant factors. The resource counts we find depend on instance-specific parameters, such as the condition number of certain linear systems within the problem. To determine the size of these parameters, we perform numerical simulations of small PO instances, which lead to concrete resource estimates for the PO use case. Our numerical results do not probe large enough instance sizes to make conclusive statements about the asymptotic scaling of the algorithm. However, already at small instance sizes, our analysis suggests that, due primarily to large constant pre-factors, poorly conditioned linear systems, and a fundamental reliance on costly quantum state tomography, fundamental improvements to the QIPM are required for it to lead to practical quantum advantage., Comment: 40 pages, 15 figures. v2: minor corrections and updates to match journal version

We introduce a versatile method for preparing a quantum state whose amplitudes are given by some known function. Unlike existing approaches, our method does not require handcrafted reversible arithmetic circuits, or quantum memory loads, to encode the function values. Instead, we use a template quantum eigenvalue transformation circuit to convert a low cost block encoding of the sine function into the desired function. Our method uses only 4 ancilla qubits (3 if the approximating polynomial has definite parity), providing order-of-magnitude qubit count reductions compared to state-of-the-art approaches, while using a similar number of Toffoli gates if the function can be well represented by a polynomial or Fourier approximation. Like black-box methods, the complexity of our approach depends on the 'L2-norm filling-fraction' of the function. We demonstrate the efficiency of our method for preparing states commonly used in quantum algorithms, such as Gaussian and Kaiser window states., Comment: 7+6 pages

Topological invariants of a dataset, such as the number of holes that survive from one length scale to another (persistent Betti numbers) can be used to analyse and classify data in machine learning applications. We present an improved quantum algorithm for computing persistent Betti numbers, and provide an end-to-end complexity analysis. Our approach provides large polynomial time improvements, and an exponential space saving, over existing quantum algorithms. Subject to gap dependencies, our algorithm obtains an almost quintic speedup in the number of datapoints over rigorous state-of-the-art classical algorithms for calculating the persistent Betti numbers to constant additive error - the salient task for applications. However, this may be reduced to closer to quadratic when compared against heuristic classical methods and observed scalings. We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest, as claimed previously. We conclude that there is currently no evidence that this is the case., Comment: 10 + 28 pages

We provide modular circuit-level implementations and resource estimates for several methods of block-encoding a dense $N\times N$ matrix of classical data to precision $\epsilon$; the minimal-depth method achieves a $T$-depth of $\mathcal{O}{(\log (N/\epsilon))},$ while the minimal-count method achieves a $T$-count of $\mathcal{O}{(N\log(1/\epsilon))}$. We examine resource tradeoffs between the different approaches, and we explore implementations of two separate models of quantum random access memory (QRAM). As part of this analysis, we provide a novel state preparation routine with $T$-depth $\mathcal{O}{(\log (N/\epsilon))}$, improving on previous constructions with scaling $\mathcal{O}{(\log^2 (N/\epsilon))}$. Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.

We show that the proof of the generalised quantum Stein's lemma [Brand\~ao & Plenio, Commun. Math. Phys. 295, 791 (2010)] is not correct due to a gap in the argument leading to Lemma III.9. Hence, the main achievability result of Brand\~ao & Plenio is not known to hold. This puts into question a number of established results in the literature, in particular the reversibility of quantum entanglement [Brand\~ao & Plenio, Commun. Math. Phys. 295, 829 (2010); Nat. Phys. 4, 873 (2008)] and of general quantum resources [Brand\~ao & Gour, Phys. Rev. Lett. 115, 070503 (2015)] under asymptotically resource non-generating operations. We discuss potential ways to recover variants of the newly unsettled results using other approaches., Comment: 28 pages; in v2 we added Section V.D and Section VI, and corrected several small typos; v3 is close to the published version

Divergence chain rules for channels relate the divergence of a pair of channel inputs to the divergence of the corresponding channel outputs. An important special case of such a rule is the data-processing inequality, which tells us that if the same channel is applied to both inputs then the divergence cannot increase. Based on direct matrix analysis methods, we derive several R\'enyi divergence chain rules for channels in the quantum setting. Our results simplify and in some cases generalise previous derivations in the literature., Comment: v2: 6 pages, technical note, will appear at IEEE International Symposium on Information Theory 2022, final version with updated references

The moderate deviation regime is concerned with the finite block length trade-off between communication cost and error for information processing tasks in the asymptotic regime, where the communication cost approaches a capacity-like quantity and the error vanishes at the same time. We find exact characterisations of these trade-offs for a variety of fully quantum communication tasks, including quantum source coding, quantum state splitting, entanglement-assisted quantum channel coding, and entanglement-assisted quantum channel simulation. The main technical tool we derive is a tight relation between the partially smoothed max-information and the hypothesis testing relative entropy. This allows us to obtain the expansion of the partially smoothed max-information for i.i.d. states in the moderate deviation regime., Comment: 32 pages

Phase estimation is a quantum algorithm for measuring the eigenvalues of a Hamiltonian. We propose and rigorously analyse a randomized phase estimation algorithm with two distinctive features. First, our algorithm has complexity independent of the number of terms L in the Hamiltonian. Second, unlike previous L-independent approaches, such as those based on qDRIFT, all sources of error in our algorithm can be suppressed by collecting more data samples, without increasing the circuit depth., Comment: 5+20 pages, 4 figures

It is known that distillation in continuous variable resource theories is impossible when restricted to Gaussian states and operations. To overcome this limitation, we enlarge the theories to include convex mixtures of Gaussian states and operations. This extension is operationally well-motivated since classical randomness is easily accessible. We find that resource distillation becomes possible for convex Gaussian resource theories-albeit in a limited fashion. We derive this limitation by studying the convex roof extension of a Gaussian resource measure and then go on to show that our bound is tight by means of example protocols for the distillation of squeezing and entanglement., Comment: 10+5 pages, 7 figures

We present an end-to-end and practical randomness amplification and privatisation protocol based on Bell tests. This allows the building of device-independent random number generators which output (near-)perfectly unbiased and private numbers, even if using an uncharacterised quantum device potentially built by an adversary. Our generation rates are linear in the repetition rate of the quantum device and the classical randomness post-processing has quasi-linear complexity - making it efficient on a standard personal laptop. The statistical analysis is also tailored for real-world quantum devices. Our protocol is then showcased on several different quantum computers. Although not purposely built for the task, we show that quantum computers can run faithful Bell tests by adding minimal assumptions. In this semi-device-independent manner, our protocol generates (near-)perfectly unbiased and private random numbers on today's quantum computers., Comment: As published in the journal Quantum, 33+23 pages (15 figures and 2 tables)

We give a converging semidefinite programming hierarchy of outer approximations for the set of quantum correlations of fixed dimension and derive analytical bounds on the convergence speed of the hierarchy. In particular, we give a semidefinite program of size $\exp(\mathcal{O}\big(T^{12}(\log^2(AT)+\log(Q)\log(AT))/\epsilon^2\big))$ to compute additive $\epsilon$-approximations on the values of two-player free games with $T\times T$-dimensional quantum assistance, where $A$ and $Q$ denote the numbers of answers and questions of the game, respectively. For fixed dimension $T$, this scales polynomially in $Q$ and quasi-polynomially in $A$, thereby improving on previously known approximation algorithms for which worst-case run-time guarantees are at best exponential in $Q$ and $A$. For the proof, we make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints. We also derive an informationally complete measurement which minimises the loss in distinguishability relative to the quantum side information - which may be of independent interest., Comment: v3: 20+14 pages, 1 figure, updated title, extended version

Due to Csiszar and Koerner, the private capacity of classical wiretap channels has a single-letter characterization in terms of the private information. For quantum wiretap channels, however, it is known that regularization of the private information is necessary to reach the capacity. Here, we study hybrid classical-quantum wiretap channels in order to resolve to what extent quantum effects are needed to witness non-additivity phenomena in quantum Shannon theory. For wiretap channels with quantum inputs but classical outputs, we prove that the characterization of the capacity in terms of the private information stays single-letter. Hence, entangled input states are of no asymptotic advantage in this setting. For wiretap channels with classical inputs, we show by means of explicit examples that the private information already becomes non-additive when either one of the two receivers becomes quantum (with the other receiver staying classical). This gives non-additivity examples that are not caused by entanglement and illustrates that quantum adversaries are strictly different from classical adversaries in the wiretap model., Comment: v2: updates from review process; 13 pages, 4 figures v1: 8+6 pages, 2 figures

Recent understanding of the thermodynamics of small-scale systems have enabled the characterization of the thermodynamic requirements of implementing quantum processes for fixed input states. Here, we extend these results to construct optimal universal implementations of a given process, that is, implementations that are accurate for any possible input state even after many independent and identically distributed (i.i.d.) repetitions of the process. We find that the optimal work cost rate of such an implementation is given by the thermodynamic capacity of the process, which is a single-letter and additive quantity defined as the maximal difference in relative entropy to the thermal state between the input and the output of the channel. As related results we find a new single-shot implementation of time-covariant processes and conditional erasure with nontrivial Hamiltonians, a new proof of the asymptotic equipartition property of the coherent relative entropy, and an optimal implementation of any i.i.d. process with thermal operations for a fixed i.i.d. input state. Beyond being a thermodynamic analogue of the reverse Shannon theorem for quantum channels, our results introduce a new notion of quantum typicality and present a thermodynamic application of convex-split methods., Comment: 46+15 pages, 2 figures. The appendix of arXiv:1807.05610 was split off and reworked into this technical companion paper. Version v2 reflects the journal accepted version but is extended with some additional related results (Section 8) that are not included in the published work

One-shot information theory entertains a plethora of entropic quantities, such as the smooth max-divergence, hypothesis testing divergence and information spectrum divergence, that characterize various operational tasks and are used to prove the asymptotic behavior of various tasks in quantum information theory. Tight inequalities between these quantities are thus of immediate interest. In this note we use a minimax approach (appearing previously for example in the proofs of the quantum substate theorem), to simplify the quantum problem to a commutative one, which allows us to derive such inequalities. Our derivations are conceptually different from previous arguments and in some cases lead to tighter relations. We hope that the approach discussed here can lead to progress in open problems in quantum Shannon theory, and exemplify this by applying it to a simple case of the joint smoothing problem.

The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorous a priori and a posteriori bounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments., Comment: v4: 22 pages, 4 figures, new title

We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form $\mathrm{Tr}\big[M(X\otimes Y)\big]$, maximized with respect to semidefinite constraints on $X$ and $Y$. Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans.~Inf.~Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brand\~ao & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from $O(d^{k/2})$ to $\mathrm{poly}(d,k)$, where $d$ denotes local dimension and $k$ the number of copies., Comment: 33 pages, New Title, v3

It is well known that for the discrimination of classical and quantum channels in the finite, non-asymptotic regime, adaptive strategies can give an advantage over non-adaptive strategies. However, Hayashi [IEEE Trans. Inf. Theory 55(8), 3807 (2009)] showed that in the asymptotic regime, the exponential error rate for the discrimination of classical channels is not improved in the adaptive setting. We extend this result in several ways. First, we establish the strong Stein's lemma for classical-quantum channels by showing that asymptotically the exponential error rate for classical-quantum channel discrimination is not improved by adaptive strategies. Second, we recover many other classes of channels for which adaptive strategies do not lead to an asymptotic advantage. Third, we give various converse bounds on the power of adaptive protocols for general asymptotic quantum channel discrimination. Intriguingly, it remains open whether adaptive protocols can improve the exponential error rate for quantum channel discrimination in the asymmetric Stein setting. Our proofs are based on the concept of amortized distinguishability of quantum channels, which we analyse using data-processing inequalities., Comment: v2: 55 pages, 4 figures, final version published in Letters in Mathematical Physics

Insights from quantum information theory show that correlation measures based on quantum entropy are fundamental tools that reveal the entanglement structure of multipartite states. In that spirit, Groisman, Popescu, and Winter [Physical Review A 72, 032317 (2005)] showed that the quantum mutual information $I(A;B)$ quantifies the minimal rate of noise needed to erase the correlations in a bipartite state of quantum systems $AB$. Here, we investigate correlations in tripartite systems $ABE$. In particular, we are interested in the minimal rate of noise needed to apply to the systems $AE$ in order to erase the correlations between $A$ and $B$ given the information in system $E$, in such a way that there is only negligible disturbance on the marginal $BE$. We present two such models of conditional decoupling, called deconstruction and conditional erasure cost of tripartite states $ABE$. Our main result is that both are equal to the conditional quantum mutual information $I(A;B|E)$ -- establishing it as an operational measure for tripartite quantum correlations., Comment: 6 pages, 1 figure, see companion paper at arXiv:1609.06994

Smooth entropies are a tool for quantifying resource trade-offs in (quantum) information theory and cryptography. In typical bi- and multi-partite problems, however, some of the sub-systems are often left unchanged and this is not reflected by the standard smoothing of information measures over a ball of close states. We propose to smooth instead only over a ball of close states which also have some of the reduced states on the relevant sub-systems fixed. This partial smoothing of information measures naturally allows to give more refined characterizations of various information-theoretic problems in the one-shot setting. In particular, we immediately get asymptotic second-order characterizations for tasks such as privacy amplification against classical side information or classical state splitting. For quantum problems like state merging the general resource trade-off is tightly characterized by partially smoothed information measures as well., Comment: v2: slightly improved achievability bound for classical state splitting + fixed converse proof for privacy amplification, 25 pages

Thermodynamics imposes restrictions on what state transformations are possible. In the macroscopic limit of asymptotically many independent copies of a state---as for instance in the case of an ideal gas---the possible transformations become reversible and are fully characterized by the free energy. In this Letter, we present a thermodynamic resource theory for quantum processes that also becomes reversible in the macroscopic limit, a property that is especially rare for a resource theory of quantum channels. We identify a unique single-letter and additive quantity, the thermodynamic capacity, that characterizes the "thermodynamic value" of a quantum channel, in the sense that the work required to simulate many repetitions of a quantum process employing many repetitions of another quantum process becomes equal to the difference of the respective thermodynamic capacities. On a technical level, we provide asymptotically optimal constructions of universal implementations of quantum processes. A challenging aspect of this construction is the apparent necessity to coherently combine thermal engines that would run in different thermodynamic regimes depending on the input state. Our results have applications in quantum Shannon theory by providing a generalized notion of quantum typical subspaces and by giving an operational interpretation to the entropy difference of a channel., Comment: 6 pages, 2 figures, journal version. The technical appendix was split off into a companion paper that will be submitted separately (cf. today's arXiv listing)

We study the general framework of quantum channel simulation, that is, the ability of a quantum channel to simulate another one using different classes of codes. First, we show that the minimum error of simulation and the one-shot quantum simulation cost under no-signalling assisted codes are given by semidefinite programs. Second, we introduce the channel's smooth max-information, which can be seen as a one-shot generalization of the mutual information of a quantum channel. We provide an exact operational interpretation of the channel's smooth max-information as the one-shot quantum simulation cost under no-signalling assisted codes, which significantly simplifies the study of channel simulation and provides insights and bounds for the case under entanglement-assisted codes. Third, we derive the asymptotic equipartition property of the channel's smooth max-information; i.e., it converges to the quantum mutual information of the channel in the independent and identically distributed asymptotic limit. This implies the quantum reverse Shannon theorem in the presence of no-signalling correlations. Finally, we explore the simulation cost of various quantum channels., Comment: 21 pages, 3 figures; close to published version

We study thermal states of strongly interacting quantum spin chains and prove that those can be represented in terms of convex combinations of matrix product states. Apart from revealing new features of the entanglement structure of Gibbs states our results provide a theoretical justification for the use of White's algorithm of minimally entangled typical thermal states. Furthermore, we shed new light on time dependent matrix product state algorithms which yield hydrodynamical descriptions of the underlying dynamics., Comment: v3: 10 pages, 2 figures, final published version

We extend quantum Stein's lemma in asymmetric quantum hypothesis testing to composite null and alternative hypotheses. As our main result, we show that the asymptotic error exponent for testing convex combinations of quantum states $\rho^{\otimes n}$ against convex combinations of quantum states $\sigma^{\otimes n}$ can be written as a regularized quantum relative entropy formula. We prove that in general such a regularization is needed but also discuss various settings where our formula as well as extensions thereof become single-letter. This includes an operational interpretation of the relative entropy of coherence in terms of hypothesis testing. For our proof, we start from the composite Stein's lemma for classical probability distributions and lift the result to the non-commutative setting by using elementary properties of quantum entropy. Finally, our findings also imply an improved recoverability lower bound on the conditional quantum mutual information in terms of the regularized quantum relative entropy -- featuring an explicit and universal recovery map., Comment: 14 pages, v2: matches published version, includes several corrections

Given an entanglement measure $E$, the entanglement of a quantum channel is defined as the largest amount of entanglement $E$ that can be generated from the channel, if the sender and receiver are not allowed to share a quantum state before using the channel. The amortized entanglement of a quantum channel is defined as the largest net amount of entanglement $E$ that can be generated from the channel, if the sender and receiver are allowed to share an arbitrary state before using the channel. Our main technical result is that amortization does not enhance the entanglement of an arbitrary quantum channel, when entanglement is quantified by the max-Rains relative entropy. We prove this statement by employing semi-definite programming (SDP) duality and SDP formulations for the max-Rains relative entropy and a channel's max-Rains information, found recently in [Wang et al., arXiv:1709.00200]. The main application of our result is a single-letter, strong-converse, and efficiently computable upper bound on the capacity of a quantum channel for transmitting qubits when assisted by positive-partial-transpose preserving (PPT-P) channels between every use of the channel. As the class of local operations and classical communication (LOCC) is contained in PPT-P, our result establishes a benchmark for the LOCC-assisted quantum capacity of an arbitrary quantum channel, which is relevant in the context of distributed quantum computation and quantum key distribution., Comment: v2: 24 pages, 1 figure, final version accepted for publication in New Journal of Physics