David Sutter

Last Name

Sutter

First Name

David

ORCID

0000-0001-9779-8888

Show all metadata

Search Results

Publications 1 - 10 of 31

Cutting circuits with multiple two-qubit unitaries
Schmitt, Lukas; Piveteau, Christophe; Sutter, David (2025)
Quantum
Quasiprobabilistic cutting techniques allow us to partition large quantum circuits into smaller sub circuits by replacing non-local gates with probabilistic mixtures of local gates. The cost of this method is a sampling overhead that scales exponentially in the number of cuts. It is crucial to determine the minimal cost for gate cutting and to understand whether allowing for classical communication between sub circuits can improve the sampling overhead. In this work, we derive a closed formula for the optimal sampling overhead for cutting an arbitrary number of two-qubit unitaries and provide the corresponding decomposition. We find that cutting several arbitrary two-qubit unitaries together is cheaper than cutting them individually and classical communication does not give any advantage.
Circuit cutting with classical side information
Piveteau, Christophe; Schmitt, Lukas; Sutter, David (2025)
Physical Review Research
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 from these subcircuits are then combined in classical postprocessing to accurately reconstruct the expectation value of the original circuit. Circuit cutting introduces a sampling overhead that grows exponentially with the number of gates and qubit wires that are cut. Many recently developed quasiprobabilistic circuit cutting techniques leverage classical side information, obtained from intermediate measurements within the subcircuits, to enhance the postprocessing step. In this work, we provide a formalization of general circuit cutting techniques utilizing side information through quantum instruments. With this framework, we analyze the advantage that classical side information provides in reducing the sampling overhead of circuit cutting. Surprisingly, we find that in certain scenarios, side information does not yield any reduction in sampling overhead, whereas in others it is essential for circuit cutting to be feasible at all. Furthermore, we present a lower bound for the optimal sampling overhead with side information that can be evaluated efficiently via semidefinite programming and improves on all previously known lower bounds.
Bounds on Lyapunov Exponents via Entropy Accumulation
Sutter, David; Fawzi, Omar; Renner, Renato (2021)
IEEE Transactions on Information Theory
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. By establishing a link between Lyapunov exponents and an information theoretic tool called entropy accumulation theorem we derive an upper and a lower bound for the maximal and minimal Lyapunov exponent, respectively. The bounds assume independence of the random matrices, are analytical, and are tight in the commutative case as well as in other scenarios. They can be expressed in terms of an optimization problem that only involves single matrices rather than large products. The upper bound for the maximal Lyapunov exponent can be evaluated efficiently via the theory of convex optimization.
Error Mitigation for Universal Gates on Encoded Qubits
Piveteau, Christophe; Sutter, David; Bravyi, Sergey; et al. (2021)
Physical Review Letters
The Eastin-Knill theorem states that no quantum error-correcting code can have a universal set of transversal gates. For Calderbank-Shor-Steane codes that can implement Clifford gates transversally, it suffices to provide one additional non-Clifford gate, such as the T gate, to achieve universality. Common methods to implement fault-tolerant T gates, e.g., magic state distillation, generate a significant hardware overhead that will likely prevent their practical usage in the near-term future. Recently, methods have been developed to mitigate the effect of noise in shallow quantum circuits that are not protected by error correction. Error mitigation methods require no additional hardware resources but suffer from a bad asymptotic scaling and apply only to a restricted class of quantum algorithms. In this Letter, we combine both approaches and show how to implement encoded Clifford+T circuits where Clifford gates are protected from noise by error correction while errors introduced by noisy encoded T gates are mitigated using the quasiprobability method. As a result, Clifford+T circuits with a number of T gates inversely proportional to the physical noise rate can be implemented on small error-corrected devices without magic state distillation. We argue that such circuits can be out of reach for state-of-the-art classical simulation algorithms.
Universal Recovery Maps and Approximate Sufficiency of Quantum Relative Entropy
Junge, Marius; Renner, Renato; Sutter, David; et al. (2018)
Annales Henri Poincaré
The data processing inequality states that the quantum relative entropy between two states ρ and σ can never increase by applying the same quantum channel N to both states. This inequality can be strengthened with a remainder term in the form of a distance between ρ and the closest recovered state (R∘N)(ρ), where R is a recovery map with the property that σ=(R∘N)(σ). We show the existence of an explicit recovery map that is universal in the sense that it depends only on σ and the quantum channel N to be reversed. This result gives an alternate, information-theoretic characterization of the conditions for approximate quantum error correction.
Quasiprobability decompositions with reduced sampling overhead
Piveteau, Christophe; Sutter, David; Woerner, Stefan (2022)
npj Quantum Information
Quantum error-mitigation techniques can reduce noise on current quantum hardware without the need for fault-tolerant quantum error correction. For instance, the quasiprobability method simulates a noise-free quantum computer using a noisy one, with the caveat of only producing the correct expected values of observables. The cost of this error mitigation technique manifests as a sampling overhead which scales exponentially in the number of corrected gates. In this work, we present an algorithm based on mathematical optimization that aims to choose the quasiprobability decomposition in a noise-aware manner. This directly leads to a significantly lower basis of the sampling overhead compared to existing approaches. A key element of the novel algorithm is a robust quasiprobability method that allows for a tradeoff between an approximation error and the sampling overhead via semidefinite programming.
Generalised Entropy Accumulation
Metger, Tony; Fawzi, Omar; Sutter, David; et al. (2024)
Communications in Mathematical Physics
Consider a sequential process in which each step outputs a system Ai and updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the minentropy of the outputs A1,..., An conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) (Dupuis et al. in Commun Math Phys 379: 867–913, 2020), which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition. Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. As examples, we give the first multi-round security proof for blind randomness expansion and a simplified analysis of the E91 QKD protocol. The proof of our generalised EAT relies on a new variant of Uhlmann’s theorem and new chain rules for the Rényi divergence and entropy, which might be of independent interest.
Exact and Practical Pattern Matching for Quantum Circuit Optimization
Iten, Raban; Moyard, Romain; Metger, Tony; et al. (2022)
ACM Transactions on Quantum Computing
Quantum computations are typically performed as a sequence of basic operations, called quantum gates. Different gate sequences, called quantum circuits, can implement the same overall quantum computation. Since every additional quantum gate takes time and introduces noise into the system, it is important to find the smallest possible quantum circuit that implements a given computation, especially for near-term quantum devices that can execute only a limited number of quantum gates before noise renders the computation useless. An important building block for many quantum circuit optimization techniques is pattern matching: given a large and small quantum circuit, we would like to find all maximal matches of the small circuit, called a pattern, in the large circuit, considering pairwise commutation of quantum gates. In this work, we present the first classical algorithm for pattern matching that provably finds all maximal matches and is efficient enough to be practical for circuit sizes typical for near-term devices. We demonstrate numerically that combining our algorithm with known pattern-matching-based circuit optimization techniques reduces the gate count of a random quantum circuit by ∼ 30% and can further improve practically relevant quantum circuits that were already optimized with state-of-the-art techniques.
Generalised entropy accumulation
Metger, Tony; Fawzi, Omar; Sutter, David; et al. (2022)
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
The min-entropy of a quantum system A conditioned on another quantum system E describes how much randomness can be extracted from A with respect to an adversary in possession of E. This quantity plays a crucial role in quantum cryptography: the security proofs of many quantum cryptographic protocols reduce to showing a lower bound on such a min-entropy. Here, we develop a new tool, called generalised entropy accumulation, for computing such bounds. Concretely, we consider a sequential process in which each step outputs a system A(i) and updates a side information register E. We prove that if this process satisfies a natural "non-signalling" condition between past outputs and future side information, the min-entropy of the outputs A(1),..., A(n) conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) [1], which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition. Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. In particular, it is the first general tool that is applicable to mistrustful device-independent cryptography. To demonstrate this, we give the first security proof for blind randomness expansion [2] against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution [3], and also has applications beyond quantum cryptography.
Chain Rule for the Quantum Relative Entropy
Fang, Kun; Fawzi, Omar; Renner, Renato; et al. (2020)
Physical Review Letters

Publications 1 - 10 of 31

David Sutter

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results