Publications (42)
Efficient Approximation of Quantum Channel Capacities
David Sutter, Tobias Sutter, Peyman Mohajerin Esfahani +1
We propose an iterative method for approximating the capacity of classical-quantum channels with a discrete input alphabet and a finite dimensional output, possibly under additiona…
Strengthened Monotonicity of Relative Entropy via Pinched Petz Recovery Map
David Sutter, Marco Tomamichel, Aram W. Harrow
The quantum relative entropy between two states satisfies a monotonicity property meaning that applying the same quantum channel to both states can never increase their relative en…
Quantum Kernel Alignment with Stochastic Gradient Descent
Gian Gentinetta, David Sutter, Christa Zoufal +2
Quantum support vector machines have the potential to achieve a quantum speedup for solving certain machine learning problems. The key challenge for doing so is finding good quantu…
Circuit knitting with classical communication
Christophe Piveteau, David Sutter
The scarcity of qubits is a major obstacle to the practical usage of quantum computers in the near future. To circumvent this problem, various circuit knitting techniques have been…
Effective dimension of machine learning models
Amira Abbas, David Sutter, Alessio Figalli +1
Making statements about the performance of trained models on tasks involving new data is one of the primary goals of machine learning, i.e., to understand the generalization power…
Alignment of Polarized Sets
Joseph M. Renes, David Sutter, S. Hamed Hassani
Arıkan's polar coding technique is based on the idea of synthesizing channels from the instances of the physical channel by a simple linear encoding transformation. Each s…
Error Bounds for Variational Quantum Time Evolution
Christa Zoufal, David Sutter, Stefan Woerner
Variational quantum time evolution allows us to simulate the time dynamics of quantum systems with near-term compatible quantum circuits. Due to the variational nature of this meth…
Circuit cutting with classical side information
Christophe Piveteau, Lukas Schmitt, David Sutter
Circuit cutting is a technique for simulating large quantum circuits by partitioning them into smaller subcircuits, which can be executed on smaller quantum devices. The results fr…
Almost-iid information theory
Giulia Mazzola, David Sutter, Renato Renner
Information-theoretic techniques are based on the assumption that resources are well characterized by independent and identically distributed (iid) states. This assumption cannot b…
An information-theoretic treatment of quantum dichotomies
Francesco Buscemi, David Sutter, Marco Tomamichel
Given two pairs of quantum states, we want to decide if there exists a quantum channel that transforms one pair into the other. The theory of quantum statistical comparison and qua…
Approximate quantum Markov chains
David Sutter
This book is an introduction to quantum Markov chains and explains how this concept is connected to the question of how well a lost quantum mechanical system can be recovered from…
Cutting circuits with multiple two-qubit unitaries
Lukas Schmitt, Christophe Piveteau, David Sutter
Quasiprobabilistic cutting techniques allow us to partition large quantum circuits into smaller subcircuits by replacing non-local gates with probabilistic mixtures of local gates.…
Quantum Legendre-Fenchel Transform
David Sutter, Giacomo Nannicini, Tobias Sutter +1
We present a quantum algorithm to compute the discrete Legendre-Fenchel transform. Given access to a convex function evaluated at points, the algorithm outputs a quantum-mechan…
Necessary criterion for approximate recoverability
David Sutter, Renato Renner
A tripartite state forms a Markov chain if there exists a recovery map acting only on the -part that perfectly reconstructs from $…
Approximate Degradable Quantum Channels
David Sutter, Volkher B. Scholz, Andreas Winter +1
Degradable quantum channels are an important class of completely positive trace-preserving maps. Among other properties, they offer a single-letter formula for the quantum and the…
Multivariate Trace Inequalities
David Sutter, Mario Berta, Marco Tomamichel
We prove several trace inequalities that extend the Golden-Thompson and the Araki-Lieb-Thirring inequality to arbitrarily many matrices. In particular, we strengthen Lieb's triple…
Pretty good measures in quantum information theory
Raban Iten, Joseph M. Renes, David Sutter
Quantum generalizations of Renyi's entropies are a useful tool to describe a variety of operational tasks in quantum information processing. Two families of such generalizations tu…
Optimal wire cutting with classical communication
Lukas Brenner, Christophe Piveteau, David Sutter
Circuit knitting is the process of partitioning large quantum circuits into smaller subcircuits such that the result of the original circuits can be deduced by only running the sub…
A Two-Scale Complexity Measure for Deep Learning Models
Massimiliano Datres, Gian Paolo Leonardi, Alessio Figalli +1
We introduce a novel capacity measure 2sED for statistical models based on the effective dimension. The new quantity provably bounds the generalization error under mild assumptions…
Bounds on Lyapunov exponents via entropy accumulation
David Sutter, Omar Fawzi, Renato Renner
Lyapunov exponents describe the asymptotic behavior of the singular values of large products of random matrices. A direct computation of these exponents is however often infeasible…
Achieving the Capacity of any DMC using only Polar Codes
David Sutter, Joseph M. Renes, Frédéric Dupuis +1
We construct a channel coding scheme to achieve the capacity of any discrete memoryless channel based solely on the techniques of polar coding. In particular, we show how source po…
Approximate Quantum Fourier Transform in Logarithmic Depth on a Line
Elisa Bäumer, David Sutter, Stefan Woerner
The approximate quantum Fourier transform (AQFT) on qubits can be implemented in logarithmic depth using qubits with all-to-all connectivity, as shown in [Hales, PhD Thesi…
Universal Polar Codes for More Capable and Less Noisy Channels and Sources
David Sutter, Joseph M. Renes
We prove two results on the universality of polar codes for source coding and channel communication. First, we show that for any polar code built for a source there exist…
Generalised entropy accumulation
Tony Metger, Omar Fawzi, David Sutter +1
Consider a sequential process in which each step outputs a system and updates a side information register . We prove that if this process satisfies a natural "non-signalli…
Quasiprobability decompositions with reduced sampling overhead
Christophe Piveteau, David Sutter, Stefan Woerner
Quantum error mitigation techniques can reduce noise on current quantum hardware without the need for fault-tolerant quantum error correction. For instance, the quasiprobability me…
Capacity of Random Channels with Large Alphabets
Tobias Sutter, David Sutter, John Lygeros
We consider discrete memoryless channels with input alphabet size and output alphabet size , where ceil for some constant . The channel transition matrix co…
Efficient Quantum Polar Codes Requiring No Preshared Entanglement
Joseph M. Renes, David Sutter, Frédéric Dupuis +1
We construct an explicit quantum coding scheme which achieves a communication rate not less than the coherent information when used to transmit quantum information over a noisy qua…
The complexity of quantum support vector machines
Gian Gentinetta, Arne Thomsen, David Sutter +1
Quantum support vector machines employ quantum circuits to define the kernel function. It has been shown that this approach offers a provable exponential speedup compared to any kn…
Robust generalized quantum Stein's lemma
Giulia Mazzola, David Sutter, Renato Renner
The generalized quantum Stein's lemma provides an explicit expression for the optimal error exponent when distinguishing many independent and identically distributed (iid) copies o…
Universal recovery map for approximate Markov chains
David Sutter, Omar Fawzi, Renato Renner
A central question in quantum information theory is to determine how well lost information can be reconstructed. Crucially, the corresponding recovery operation should perform well…
Efficient One-Way Secret-Key Agreement and Private Channel Coding via Polarization
David Sutter, Joseph M. Renes, Renato Renner
We introduce explicit schemes based on the polarization phenomenon for the tasks of one-way secret key agreement from common randomness and private channel coding. For the former t…
Efficient Approximation of Channel Capacities
Tobias Sutter, David Sutter, Peyman Mohajerin Esfahani +1
We propose an iterative method for approximately computing the capacity of discrete memoryless channels, possibly under additional constraints on the input distribution. Based on d…
The power of quantum neural networks
Amira Abbas, David Sutter, Christa Zoufal +3
Fault-tolerant quantum computers offer the promise of dramatically improving machine learning through speed-ups in computation or improved model scalability. In the near-term, howe…
Quantum Brascamp-Lieb Dualities
Mario Berta, David Sutter, Michael Walter
Brascamp-Lieb inequalities are entropy inequalities which have a dual formulation as generalized Young inequalities. In this work, we introduce a fully quantum version of this dual…
Quantitative lower bounds on the Lyapunov exponent from multivariate matrix inequalities
Marius Lemm, David Sutter
The Lyapunov exponent characterizes the asymptotic behavior of long matrix products. Recognizing scenarios where the Lyapunov exponent is strictly positive is a fundamental challen…
Error mitigation for universal gates on encoded qubits
Christophe Piveteau, David Sutter, Sergey Bravyi +2
The Eastin-Knill theorem states that no quantum error correcting code can have a universal set of transversal gates. For CSS codes that can implement Clifford gates transversally i…
Generalized maximum entropy estimation
Tobias Sutter, David Sutter, Peyman Mohajerin Esfahani +1
We consider the problem of estimating a probability distribution that maximizes the entropy while satisfying a finite number of moment constraints, possibly corrupted by noise. Bas…
A chain rule for the quantum relative entropy
Kun Fang, Omar Fawzi, Renato Renner +1
The chain rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relati…
Exact and practical pattern matching for quantum circuit optimization
Raban Iten, Romain Moyard, Tony Metger +2
Quantum computations are typically compiled into a circuit of basic quantum gates. Just like for classical circuits, a quantum compiler should optimize the quantum circuit, e.g. by…
Uhlmann's theorem for relative entropies
Giulia Mazzola, David Sutter, Renato Renner
Uhlmann's theorem states that, for any two quantum states and , there exists an extension of such that the fidelity between and …
Quantum speedups for convex dynamic programming
David Sutter, Giacomo Nannicini, Tobias Sutter +1
We present a quantum algorithm to solve dynamic programming problems with convex value functions. For linear discrete-time systems with a -dimensional state space of size , t…
Universal recovery maps and approximate sufficiency of quantum relative entropy
Marius Junge, Renato Renner, David Sutter +2
The data processing inequality states that the quantum relative entropy between two states and can never increase by applying the same quantum channel to bo…