David Gross
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
David Gross has a total of 52 co-authors. Here are the top co-authors by number of shared publications:
- Jens Eisert
Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Berlin, Germany
2 shared publications - Johan Aberg
Institute for Theoretical Physics, University of Cologne, Cologne, Germany
2 shared publications - Michael Walter
Stanford Institute for Theoretical Physics Stanford University Kavli Institute for Theoretical Physics
2 shared publications - Richard Kueng
Institute for Quantum Information and Matter California Institute of Technology 91125 Pasadena CA
2 shared publications - Sepehr Nezami
Stanford Institute for Theoretical Physics Stanford University Kavli Institute for Theoretical Physics
2 shared publications - Aditya Kela
Institute for Theoretical Physics, University of Cologne, 50937 Cologne, Germany
1 shared publication
Latest Publications
- Open Access
Is it Gaussian? Testing bosonic quantum states
Gaussian states are widely regarded as one of the most relevant classes of continuous-variable (CV) quantum states, as they naturally arise in physical systems and play a key role in quantum technologies. This motivates a fundamental question: given copies of an unknown CV state, how can we efficiently test whether it is Gaussian? We address this problem from the perspective of representation theory and quantum learning theory, characterizing the sample complexity of Gaussianity testing as a function of the number of modes. For pure states, we prove that just a constant number of copies is sufficient to decide whether the state is exactly Gaussian. We then extend this to the tolerant setting, showing that a polynomial number of copies suffices to distinguish states that are close to Gaussian from those that are far. In contrast, we establish that testing Gaussianity of general mixed states necessarily requires exponentially many copies, thereby identifying a fundamental limitation in testing CV systems. Our approach relies on rotation-invariant symmetries of Gaussian states together with the recently introduced toolbox of CV trace-distance bounds.
Open AccessIs it Gaussian? Testing bosonic quantum states
Gaussian states are widely regarded as one of the most relevant classes of continuous-variable (CV) quantum states, as they naturally arise in physical systems and play a key role in quantum technologies. This motivates a fundamental question: given copies of an unknown CV state, how can we efficiently test whether it is Gaussian? We address this problem from the perspective of representation theory and quantum learning theory, characterizing the sample complexity of Gaussianity testing as a function of the number of modes. For pure states, we prove that just a constant number of copies is sufficient to decide whether the state is exactly Gaussian. We then extend this to the tolerant setting, showing that a polynomial number of copies suffices to distinguish states that are close to Gaussian from those that are far. In contrast, we establish that testing Gaussianity of general mixed states necessarily requires exponentially many copies, thereby identifying a fundamental limitation in testing CV systems. Our approach relies on rotation-invariant symmetries of Gaussian states together with the recently introduced toolbox of CV trace-distance bounds.
- Open Access
- 22 April 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 6, 1-22
Runtime–Coherence Tradeoffs for Hybrid Satisfiability Solvers
Many search-based quantum algorithms that achieve a theoretical speed-up are not practically relevant since they require extraordinarily long coherence times, or lack the parallelizability of their classical counterparts. This raises the question of how to divide computational tasks into a collection of parallelizable subproblems, each of which can be solved by a quantum computer with limited coherence time. Here, we approach this question via hybrid algorithms for the $k$-SAT problem. Our analysis is based on Schöning's algorithm, which solves instances of $k$-SAT by performing random walks in the space of potential assignments. The search space of the walk allows for ‘natural’ partitions, where we subject only one part of the partition to a Grover search, while the rest is sampled classically, thus resulting in a hybrid scheme. In this setting, we argue that there exists a simple trade-off relation between the total runtime and the coherence-time, which no such partition based hybrid-scheme can surpass. For several concrete choices of partitions, we explicitly determine the specific runtime coherence-time relations, and show saturation of the ideal trade-off. Finally, we present numerical simulations which suggest additional flexibility in implementing hybrid algorithms with optimal trade-off.
- 22 April 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 6, 1-22
Open AccessRuntime–Coherence Tradeoffs for Hybrid Satisfiability Solvers
Many search-based quantum algorithms that achieve a theoretical speed-up are not practically relevant since they require extraordinarily long coherence times, or lack the parallelizability of their classical counterparts. This raises the question of how to divide computational tasks into a collection of parallelizable subproblems, each of which can be solved by a quantum computer with limited coherence time. Here, we approach this question via hybrid algorithms for the $k$-SAT problem. Our analysis is based on Schöning's algorithm, which solves instances of $k$-SAT by performing random walks in the space of potential assignments. The search space of the walk allows for ‘natural’ partitions, where we subject only one part of the partition to a Grover search, while the rest is sampled classically, thus resulting in a hybrid scheme. In this setting, we argue that there exists a simple trade-off relation between the total runtime and the coherence-time, which no such partition based hybrid-scheme can surpass. For several concrete choices of partitions, we explicitly determine the specific runtime coherence-time relations, and show saturation of the ideal trade-off. Finally, we present numerical simulations which suggest additional flexibility in implementing hybrid algorithms with optimal trade-off.
- 1 November 2024
- Published by AIP Publishing in Journal of Mathematical Physics
- Vol. 65 (11)
Wigner’s theorem for stabilizer states and quantum designs
We describe the symmetry group of the stabilizer polytope for any number n of systems and any prime local dimension d. In the qubit case, the symmetry group coincides with the linear and anti-linear Clifford operations. In the case of qudits, the structure is somewhat richer: For n = 1, it is a wreath product of permutations of bases and permutations of the elements within each basis. For n > 1, the symmetries are given by affine symplectic similitudes. These are the affine maps that preserve the symplectic form of the underlying discrete phase space up to a non-zero multiplier. We phrase these results with respect to a number of a priori different notions of “symmetry,” including Kadison symmetries (bijections that are compatible with convex combinations), Wigner symmetries (bijections that preserve inner products), and symmetries realized by an action on Hilbert space. Going beyond stabilizer states, we extend an observation of Heinrich and Gross [Quantum 3, 132 (2019)] and show that the symmetries of fairly general sets of Hermitian operators are constrained by certain moments. In particular: the symmetries of a set that behaves like a 3-design preserve Jordan products and are therefore realized by conjugation with unitaries or anti-unitaries. (The structure constants of the Jordan algebra are encoded in an order-three tensor, which we connect to the third moments of a design). This generalizes Kadison’s formulation of the classic Wigner theorem on quantum mechanical symmetries.
- 1 November 2024
- Published by AIP Publishing in Journal of Mathematical Physics
- Vol. 65 (11)
Wigner’s theorem for stabilizer states and quantum designs
We describe the symmetry group of the stabilizer polytope for any number n of systems and any prime local dimension d. In the qubit case, the symmetry group coincides with the linear and anti-linear Clifford operations. In the case of qudits, the structure is somewhat richer: For n = 1, it is a wreath product of permutations of bases and permutations of the elements within each basis. For n > 1, the symmetries are given by affine symplectic similitudes. These are the affine maps that preserve the symplectic form of the underlying discrete phase space up to a non-zero multiplier. We phrase these results with respect to a number of a priori different notions of “symmetry,” including Kadison symmetries (bijections that are compatible with convex combinations), Wigner symmetries (bijections that preserve inner products), and symmetries realized by an action on Hilbert space. Going beyond stabilizer states, we extend an observation of Heinrich and Gross [Quantum 3, 132 (2019)] and show that the symmetries of fairly general sets of Hermitian operators are constrained by certain moments. In particular: the symmetries of a set that behaves like a 3-design preserve Jordan products and are therefore realized by conjugation with unitaries or anti-unitaries. (The structure constants of the Jordan algebra are encoded in an order-three tensor, which we connect to the third moments of a design). This generalizes Kadison’s formulation of the classic Wigner theorem on quantum mechanical symmetries.
- 28 August 2024
- Published by American Physical Society (APS) in Physical Review A
- Vol. 110 (2) , 022225
Entanglement swapping in generalized probabilistic theories and iterated Clauser-Horne-Shimony-Holt games
While there exist theories that have states more strongly entangled than quantum theory, in the sense that they show Clauser-Horne-Shimony-Holt (CHSH) values above Tsirelson's bound, all known examples of such theories have a strictly smaller set of measurements. Therefore, in tasks that require both bipartite states and measurements, they do not perform better than quantum mechanics. One of the simplest information processing tasks involving both bipartite states and measurements is that of entanglement swapping. In this paper, we study entanglement swapping in generalized probabilistic theories (GPTs). In particular, we introduce the iterated CHSH game, which measures the power of a GPT to preserve nonclassical correlations, in terms of the largest CHSH value obtainable after rounds of entanglement swapping. Our main result is the construction of a GPT that achieves a CHSH value of 4 after an arbitrary number of rounds. This addresses a question about the optimality of quantum theory for such games recently raised by Weilenmann and Colbeck. One challenge faced when treating this problem is that there seems to be no general framework for constructing GPTs in which entanglement swapping is a well-defined operation. Therefore, we introduce an algorithmic construction that turns a bipartite GPT into a multipartite GPT that supports entanglement swapping, if consistently possible.- 28 August 2024
- Published by American Physical Society (APS) in Physical Review A
- Vol. 110 (2) , 022225
Entanglement swapping in generalized probabilistic theories and iterated Clauser-Horne-Shimony-Holt games
While there exist theories that have states more strongly entangled than quantum theory, in the sense that they show Clauser-Horne-Shimony-Holt (CHSH) values above Tsirelson's bound, all known examples of such theories have a strictly smaller set of measurements. Therefore, in tasks that require both bipartite states and measurements, they do not perform better than quantum mechanics. One of the simplest information processing tasks involving both bipartite states and measurements is that of entanglement swapping. In this paper, we study entanglement swapping in generalized probabilistic theories (GPTs). In particular, we introduce the iterated CHSH game, which measures the power of a GPT to preserve nonclassical correlations, in terms of the largest CHSH value obtainable after rounds of entanglement swapping. Our main result is the construction of a GPT that achieves a CHSH value of 4 after an arbitrary number of rounds. This addresses a question about the optimality of quantum theory for such games recently raised by Weilenmann and Colbeck. One challenge faced when treating this problem is that there seems to be no general framework for constructing GPTs in which entanglement swapping is a well-defined operation. Therefore, we introduce an algorithmic construction that turns a bipartite GPT into a multipartite GPT that supports entanglement swapping, if consistently possible.- Open Access
Realistic Runtime Analysis for Quantum Simplex Computation
In recent years, strong expectations have been raised for the possible power of quantum computing for solving difficult optimization problems, based on theoretical, asymptotic worst-case bounds. Can we expect this to have consequences for Linear and Integer Programming when solving instances of practically relevant size, a fundamental goal of Mathematical Programming, Operations Research and Algorithm Engineering? Answering this question faces a crucial impediment: The lack of sufficiently large quantum platforms prevents performing real-world tests for comparison with classical methods. In this paper, we present a quantum analog for classical runtime analysis when solving real-world instances of important optimization problems. To this end, we measure the expected practical performance of quantum computers by analyzing the expected gate complexity of a quantum algorithm. The lack of practical quantum platforms for experimental comparison is addressed by hybrid benchmarking, in which the algorithm is performed on a classical system, logging the expected cost of the various subroutines that are employed by the quantum versions. In particular, we provide an analysis of quantum methods for Linear Programming, for which recent work has provided asymptotic speedup through quantum subroutines for the Simplex method. We show that a practical quantum advantage for realistic problem sizes would require quantum gate operation times that are considerably below current physical limitations.
Open AccessRealistic Runtime Analysis for Quantum Simplex Computation
In recent years, strong expectations have been raised for the possible power of quantum computing for solving difficult optimization problems, based on theoretical, asymptotic worst-case bounds. Can we expect this to have consequences for Linear and Integer Programming when solving instances of practically relevant size, a fundamental goal of Mathematical Programming, Operations Research and Algorithm Engineering? Answering this question faces a crucial impediment: The lack of sufficiently large quantum platforms prevents performing real-world tests for comparison with classical methods. In this paper, we present a quantum analog for classical runtime analysis when solving real-world instances of important optimization problems. To this end, we measure the expected practical performance of quantum computers by analyzing the expected gate complexity of a quantum algorithm. The lack of practical quantum platforms for experimental comparison is addressed by hybrid benchmarking, in which the algorithm is performed on a classical system, logging the expected cost of the various subroutines that are employed by the quantum versions. In particular, we provide an analysis of quantum methods for Linear Programming, for which recent work has provided asymptotic speedup through quantum subroutines for the Simplex method. We show that a practical quantum advantage for realistic problem sizes would require quantum gate operation times that are considerably below current physical limitations.
- 22 October 2022
- Published by Springer Nature
- p. 37-75
Proof Methods for Robust Low-Rank Matrix Recovery
- 22 October 2022
- Published by Springer Nature
- p. 37-75
Proof Methods for Robust Low-Rank Matrix Recovery
- Open Access
- 30 September 2022
- Published by Walter de Gruyter GmbH in Mitteilungen der Deutschen Mathematiker-Vereinigung
- Vol. 30 (3) , 215
Neue Mitglieder: Habilitationen und Promotionen, Die DMV und Impressum
Article Neue Mitglieder: Habilitationen und Promotionen, Die DMV und Impressum was published on September 30, 2022 in the journal Mitteilungen der Deutschen Mathematiker-Vereinigung (volume 30, issue 3).
- 30 September 2022
- Published by Walter de Gruyter GmbH in Mitteilungen der Deutschen Mathematiker-Vereinigung
- Vol. 30 (3) , 215
Open AccessNeue Mitglieder: Habilitationen und Promotionen, Die DMV und Impressum
Article Neue Mitglieder: Habilitationen und Promotionen, Die DMV und Impressum was published on September 30, 2022 in the journal Mitteilungen der Deutschen Mathematiker-Vereinigung (volume 30, issue 3).
- Top Cited PapersOpen Access
- 29 June 2021
- Published by Springer Nature in Communications in Mathematical Physics
- Vol. 385 (3) , 1325-1393
Schur–Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
Schur–Weyl duality is a ubiquitous tool in quantum information. At its heart is the statement that the space of operators that commute with the t-fold tensor powers $$U^{\otimes t}$$ of all unitaries $$U\in U(d)$$ is spanned by the permutations of the t tensor factors. In this work, we describe a similar duality theory for tensor powers of Clifford unitaries. The Clifford group is a central object in many subfields of quantum information, most prominently in the theory of fault-tolerance. The duality theory has a simple and clean description in terms of finite geometries. We demonstrate its effectiveness in several applications: We resolve an open problem in quantum property testing by showing that “stabilizerness” is efficiently testable: There is a protocol that, given access to six copies of an unknown state, can determine whether it is a stabilizer state, or whether it is far away from the set of stabilizer states. We give a related membership test for the Clifford group. We find that tensor powers of stabilizer states have an increased symmetry group. Conversely, we provide corresponding de Finetti theorems, showing that the reductions of arbitrary states with this symmetry are well-approximated by mixtures of stabilizer tensor powers (in some cases, exponentially well). We show that the distance of a pure state to the set of stabilizers can be lower-bounded in terms of the sum-negativity of its Wigner function. This gives a new quantitative meaning to the sum-negativity (and the related mana) – a measure relevant to fault-tolerant quantum computation. The result constitutes a robust generalization of the discrete Hudson theorem. We show that complex projective designs of arbitrary order can be obtained from a finite number (independent of the number of qudits) of Clifford orbits. To prove this result, we give explicit formulas for arbitrary moments of random stabilizer states.- 29 June 2021
- Published by Springer Nature in Communications in Mathematical Physics
- Vol. 385 (3) , 1325-1393
Top Cited PapersOpen AccessSchur–Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
Schur–Weyl duality is a ubiquitous tool in quantum information. At its heart is the statement that the space of operators that commute with the t-fold tensor powers $$U^{\otimes t}$$ of all unitaries $$U\in U(d)$$ is spanned by the permutations of the t tensor factors. In this work, we describe a similar duality theory for tensor powers of Clifford unitaries. The Clifford group is a central object in many subfields of quantum information, most prominently in the theory of fault-tolerance. The duality theory has a simple and clean description in terms of finite geometries. We demonstrate its effectiveness in several applications: We resolve an open problem in quantum property testing by showing that “stabilizerness” is efficiently testable: There is a protocol that, given access to six copies of an unknown state, can determine whether it is a stabilizer state, or whether it is far away from the set of stabilizer states. We give a related membership test for the Clifford group. We find that tensor powers of stabilizer states have an increased symmetry group. Conversely, we provide corresponding de Finetti theorems, showing that the reductions of arbitrary states with this symmetry are well-approximated by mixtures of stabilizer tensor powers (in some cases, exponentially well). We show that the distance of a pure state to the set of stabilizers can be lower-bounded in terms of the sum-negativity of its Wigner function. This gives a new quantitative meaning to the sum-negativity (and the related mana) – a measure relevant to fault-tolerant quantum computation. The result constitutes a robust generalization of the discrete Hudson theorem. We show that complex projective designs of arbitrary order can be obtained from a finite number (independent of the number of qudits) of Clifford orbits. To prove this result, we give explicit formulas for arbitrary moments of random stabilizer states. - 25 March 2021
- Published by American Mathematical Society (AMS) in Representation Theory
- Vol. 25 (8) , 193-223
Rank-deficient representations in the theta correspondence over finite fields arise from quantum codes
Let V V be a symplectic vector space and let μ \mu be the oscillator representation of Sp ( V ) \operatorname {Sp}(V) . It is natural to ask how the tensor power representation μ ⊗ t \mu ^{\otimes t} decomposes. If V V is a real vector space, then the theta correspondence asserts that there is a one-one correspondence between the irreducible subrepresentations of Sp ( V ) \operatorname {Sp}(V) and the irreps of an orthogonal group O ( t ) O(t) . It is well-known that this duality fails over finite fields. Addressing this situation, Gurevich and Howe have recently assigned a notion of rank to each Sp ( V ) \operatorname {Sp}(V) representation. They show that a variant of the Theta correspondence continues to hold over finite fields, if one restricts attention to subrepresentations of maximal rank. The nature of the rank-deficient components was left open. Here, we show that all rank-deficient Sp ( V ) \operatorname {Sp}(V) -subrepresentations arise from embeddings of lower-order tensor products of μ \mu and μ ¯ \bar \mu into μ ⊗ t \mu ^{\otimes t} . The embeddings live on spaces that have been studied in quantum information theory as tensor powers of self-orthogonal Calderbank-Shor-Steane (CSS) quantum codes . We then find that the irreducible Sp ( V ) \operatorname {Sp}(V) -subrepresentations of μ ⊗ t \mu ^{\otimes t} are labelled by the irreps of orthogonal groups O ( r ) O(r) acting on certain r r -dimensional spaces for r ≤ t r\leq t . The results hold in odd charachteristic and the “stable range” t ≤ 1 2 dim V t\leq \frac 12 \dim V . Our work has implications for the representation theory of the Clifford group . It can be thought of as a generalization of the known characterization of the invariants of the Clifford group in terms of self-dual codes.
- 25 March 2021
- Published by American Mathematical Society (AMS) in Representation Theory
- Vol. 25 (8) , 193-223
Rank-deficient representations in the theta correspondence over finite fields arise from quantum codes
Let V V be a symplectic vector space and let μ \mu be the oscillator representation of Sp ( V ) \operatorname {Sp}(V) . It is natural to ask how the tensor power representation μ ⊗ t \mu ^{\otimes t} decomposes. If V V is a real vector space, then the theta correspondence asserts that there is a one-one correspondence between the irreducible subrepresentations of Sp ( V ) \operatorname {Sp}(V) and the irreps of an orthogonal group O ( t ) O(t) . It is well-known that this duality fails over finite fields. Addressing this situation, Gurevich and Howe have recently assigned a notion of rank to each Sp ( V ) \operatorname {Sp}(V) representation. They show that a variant of the Theta correspondence continues to hold over finite fields, if one restricts attention to subrepresentations of maximal rank. The nature of the rank-deficient components was left open. Here, we show that all rank-deficient Sp ( V ) \operatorname {Sp}(V) -subrepresentations arise from embeddings of lower-order tensor products of μ \mu and μ ¯ \bar \mu into μ ⊗ t \mu ^{\otimes t} . The embeddings live on spaces that have been studied in quantum information theory as tensor powers of self-orthogonal Calderbank-Shor-Steane (CSS) quantum codes . We then find that the irreducible Sp ( V ) \operatorname {Sp}(V) -subrepresentations of μ ⊗ t \mu ^{\otimes t} are labelled by the irreps of orthogonal groups O ( r ) O(r) acting on certain r r -dimensional spaces for r ≤ t r\leq t . The results hold in odd charachteristic and the “stable range” t ≤ 1 2 dim V t\leq \frac 12 \dim V . Our work has implications for the representation theory of the Clifford group . It can be thought of as a generalization of the known characterization of the invariants of the Clifford group in terms of self-dual codes.
- Open Access
Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
Schur-Weyl duality is a ubiquitous tool in quantum information. At its heart is the statement that the space of operators that commute with the tensor powers of all unitaries is spanned by the permutations of the tensor factors. In this work, we describe a similar duality theory for tensor powers of Clifford unitaries. The Clifford group is a central object in many subfields of quantum information, most prominently in the theory of fault-tolerance. The duality theory has a simple and clean description in terms of finite geometries. We demonstrate its effectiveness in several applications: (1) We resolve an open problem in quantum property testing by showing that "stabilizerness" is efficiently testable: There is a protocol that, given access to six copies of an unknown state, can determine whether it is a stabilizer state, or whether it is far away from the set of stabilizer states. We give a related membership test for the Clifford group. (2) We find that tensor powers of stabilizer states have an increased symmetry group. We provide corresponding de Finetti theorems, showing that the reductions of arbitrary states with this symmetry are well-approximated by mixtures of stabilizer tensor powers (in some cases, exponentially well). (3) We show that the distance of a pure state to the set of stabilizers can be lower-bounded in terms of the sum-negativity of its Wigner function. This gives a new quantitative meaning to the sum-negativity (and the related mana) -- a measure relevant to fault-tolerant quantum computation. The result constitutes a robust generalization of the discrete Hudson theorem. (4) We show that complex projective designs of arbitrary order can be obtained from a finite number (independent of the number of qudits) of Clifford orbits. To prove this result, we give explicit formulas for arbitrary moments of random stabilizer states.
Open AccessSchur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
Schur-Weyl duality is a ubiquitous tool in quantum information. At its heart is the statement that the space of operators that commute with the tensor powers of all unitaries is spanned by the permutations of the tensor factors. In this work, we describe a similar duality theory for tensor powers of Clifford unitaries. The Clifford group is a central object in many subfields of quantum information, most prominently in the theory of fault-tolerance. The duality theory has a simple and clean description in terms of finite geometries. We demonstrate its effectiveness in several applications: (1) We resolve an open problem in quantum property testing by showing that "stabilizerness" is efficiently testable: There is a protocol that, given access to six copies of an unknown state, can determine whether it is a stabilizer state, or whether it is far away from the set of stabilizer states. We give a related membership test for the Clifford group. (2) We find that tensor powers of stabilizer states have an increased symmetry group. We provide corresponding de Finetti theorems, showing that the reductions of arbitrary states with this symmetry are well-approximated by mixtures of stabilizer tensor powers (in some cases, exponentially well). (3) We show that the distance of a pure state to the set of stabilizers can be lower-bounded in terms of the sum-negativity of its Wigner function. This gives a new quantitative meaning to the sum-negativity (and the related mana) -- a measure relevant to fault-tolerant quantum computation. The result constitutes a robust generalization of the discrete Hudson theorem. (4) We show that complex projective designs of arbitrary order can be obtained from a finite number (independent of the number of qudits) of Clifford orbits. To prove this result, we give explicit formulas for arbitrary moments of random stabilizer states.