Publications
Group members highlighted in bold
Preprints
- Optimal tomography of bosonic and fermionic Gaussian states
S. Chen, M. Fanizza, F. Girardi, L. Lami, F.A. Mele, M. Walter, F. Witteveen,
arXiv:2607.11847 - Traq: Estimating the Quantum Cost of Classical Programs
A. Peduri, J.K.A. Khan, G. Barthe, M. Walter,
arXiv:2509.01508 - Strassen’s support functionals coincide with the quantum functionals,
M.L. Doğan, K. Sakabe, M. Walter,
arXiv:2601.21553; accepted at FOCS’26 - Negative curvature obstructs the existence of good barriers for interior-point methods,
C. Criscitiello, H. Nieuwboer, M. Walter,
arXiv:2604.07319. - Approximate QCAs in one dimension using approximate algebras,
R. Ranard, M. Walter, F. Witteveen,
arXiv:2603.08702 - Nesterov’s accelerated gradient for unbounded convex functions finds the minimum-norm point in the dual space,
K. Sakabe,
arXiv:2602.08618 - Optimal Preconditioning is a Geodesically Convex Optimization Problem,
M.L. Doğan, A. Ergür, E. Tsigaridas,
arXiv:2512.06618 - Computing moment polytopes — with a focus on tensors, entanglement and matrix multiplication,
M. van den Berg, M. Christandl, V. Lysikov, H. Nieuwboer, M. Walter, J. Zuiddam,
arXiv.2510.08336 - Guess your neighbor's input: Quantum advantage in Feige's game,
S. Schmidt, S. Storgaard, M. Walter, Y. Zhao,
arXiv:2510.08484 - Is it Gaussian? Testing bosonic quantum states,
F. Girardi, F. Witteveen, F.A. Mele, L. Bittel, S.F.E. Oliviero, D. Gross, M. Walter,
arXiv:2510.07305; presented at QIP'26 and QCTiP'26 - Self-concordant Schrödinger operators: spectral gaps and optimization without condition numbers,
S. Gribling, S. Apers, H. Nieuwboer, M. Walter,
arXiv:2510.06115 - Matroid isomorphism games,
D. Corey, S. Schmidt, M. Wack,
arXiv:2507.06225 - Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy,
I. Klep, C. Paddock, M.-O. Renou, S. Schmidt, L. Tendick, X. Xu, Y. Zhao,
arXiv:2507.17006, accepted at QIP'26 - The moment polytope of matrix multiplication is not maximal,
M. van den Berg, M. Christandl, V. Lysikov, H. Nieuwboer, M. Walter, J. Zuiddam,
arXiv:2503.22633 - Explicit non-free tensors,
M. van den Berg, M. Christandl, V. Lysikov, H. Nieuwboer, M. Walter, J. Zuiddam,
arXiv:2503.22650 - Expressing and Analyzing Quantum Algorithms with Qualtran,
M. P. Harrigan, T. Khattar, C. Yuan, A. Peduri, N. Yosri, F. D. Malone, R. Babbush, N. C. Rubin,
arXiv:2409.04643 - Interior-point methods for unconstrained geometric programming and scaling problems,
P. Bürgisser, Y. Li, H. Nieuwboer, M. Walter,
arXiv:2008.12110 - Minimal length in an orbit closure as a semiclassical limit,
C. Franks and M. Walter,
arXiv:2004.14872
2026
- Complete Relational Logic for Infinite-Dimensional Quantum Programs with Unbounded Assertions
G. Barthe, M. Gao, J.K.A. Khan, M. Muis, I. Renison, K. Sakabe, M. Walter, Y. Xu, T. Yu, L. Zhou
Proceedings of the 41st Annual Symposium on Logic in Computer Science (LICS), 15:1-15:28 (2026) - Plethysm is in #BQP,
M. Christandl, A.W. Harrow, G. Panova, P.M. Posta, M. Walter,
Proceedings of the 41st Computational Complexity Conference (CCC), 28:1-28:11 (2026) - Fixed-Parameter Degree Bounds and Complexity of the Orbit Closure Intersection Problem for Tensors,
M.L. Doğan, J. Maar, R. Oliveira, Y. Qiao,
Proceedings of the 41st Computational Complexity Conference (CCC), 32:1-32:21 (2026) - A Computational Tsirelson’s Theorem for the Value of Compiled XOR Games,
D. Cui, G. Malavolta, A. Mehta, A. Natarajan, C. Paddock, S. Schmidt, M. Walter, T. Zhang,
Quantum 10 (2026), 1987;
also presented at TQC’24 - Interior-point methods on manifolds: theory and applications,
H. Hirai, H. Nieuwboer, M. Walter,
Foundations of Computational Mathematics (2026, in press);
Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS’23, short version) - Quantum automorphism groups of trees,
J. van Dobben de Bruyn, P. N. Kar, D. E. Roberson, S. Schmidt, P. Zeman,
Journal of Noncommutative Geometry 20 (2026), no. 2, pp. 489–505 - Exponential Asymptotics and Higher-Order Stokes Phenomenon in Singularly Perturbed ODEs,
J. Shelton, S. Crew, P.H. Trinh,
Studies in Applied Mathematics 157 (2026) - Near optimal sample complexity for matrix and tensor normal models via geodesic convexity,
C. Franks, R. Oliveira, A. Ramachandran, M. Walter,
Annals of Statistics 54, 93-119 (2026)
2025
- Computational Monogamy of Entanglement and Non-Interactive Quantum Key Distribution,
A.B. Grilo, G. Malavolta, M. Walter, T. Zhang,
Proceedings of the 23rd Theory of Cryptography Conference (TCC), 36–68 (2025) - A bound on the quantum value of all compiled nonlocal games,
A. Kulpe, G. Malavolta, C. Paddock, S. Schmidt, M. Walter,
Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) (2025),
also presented at QIP'25 (short plenary talk) - Permutation Superposition Oracles for Quantum Query Lower Bounds,
C. Majenz, G. Malavolta, M. Walter,
Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) (2025),
also presented at QIP'25 - Computing moment polytopes of tensors with applications in algebraic complexity and quantum information,
M. van den Berg, M. Christandl, V. Lysikov, H. Nieuwboer, M. Walter, J. Zuiddam,
Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) (2025) - A random purification channel for arbitrary symmetries with applications to fermions and bosons,
M. Walter, F. Witteveen,
arXiv:2512.15690 (subsumed by "Optimal tomography of bosonic and fermionic Gaussian states") - Compiled Nonlocal Games from any Trapdoor Claw-Free Function,
K. Bacho, A. Kulpe, G. Malavolta, S. Schmidt, M. Walter,
Advances in Cryptology (CRYPTO), 642-673 (2025) - Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness,
V. Lysikov and M. Walter,
Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS), 486-511 (2025) - Asymmetric graphs with quantum symmetry,
J. van Dobben de Bruyn, D. E. Roberson, S. Schmidt,
Proceedings of the London Mathematical Society (3) 131, 131:e70098 (2025) - A mathematical foundation for self-testing: Lifting common assumptions,
P. Baptista, R. Chen, J. Kaniewski, D. R. Lolck, L. Mančinska, T. G. Nielsen, S. Schmidt,
Annales Henri Poincaré (2025);
also presented QIP'24 - Algebraic Metacomplexity and Representation Theory,
M. van den Berg, P. Dutta, F. Gesmundo, C. Ikenmeyer, V. Lysikov,
Proceedings of the 40th Computational Complexity Conference (CCC), 26:1-26:35 (2025) - Resurgence, Habiro elements and strange identities,
S. Crew, V. Fantini, A. Goswami, R. Osburn, C. Wheeler,
Communications in Number Theory and Physics 19, no. 2, 289-317 (2025) - QbC: Quantum Correctness by Construction,
A. Peduri, I. Schaefer, M. Walter,
Proceedings of the ACM on Programming Languages 9, Issue OOPSLA1, 99 (2025);
also presented at PLanQC'24
2024
- The resource theory of tensor networks,
M. Christandl, V. Lysikov, V. Steffan, A. H. Werner, F. Witteveen
Quantum 8, 1560 (2024),
also presented at QIP'24 - Complexity of robust orbit problems for torus actions and the abc-conjecture,
P. Bürgisser, M. L. Doğan, V. Makam, M. Walter, A. Wigderson,
Proceedings of the 39th Computational Complexity Conference (CCC), 14:1-14:48 (2024) - Robust Quantum Public-Key Encryption with Applications to Quantum Key Distribution,
G. Malavolta and M. Walter,
Advances in Cryptology (CRYPTO), 126-151 (2024);
also presented at QIP'24 - Exponential Quantum One-Wayness and EFI Pairs,
G. Malavolta, T. Morimae, M. Walter, T. Yamakawa,
Security and Cryptography for Networks (SCN 2024) - Partial Degeneration of Tensors,
M. Christandl, F. Gesmundo, V. Lysikov, V. Steffan,
SIAM J. Matrix Analysis Appl. 45 (1), 771–800 (2024) - Random tensor networks with nontrivial links,
N. Cheng, C. Lancien, G. Penington, M. Walter, F. Witteveen,
Annales Henri Poincaré 25, 2107-2212 (2024) - Fixed-parameter debordering of Waring rank,
P. Dutta, F. Gesmundo, C. Ikenmeyer, G. Jindal, V. Lysikov,
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science (STACS), 30:1–30:15 (2024) - Persistent Tensors and Multiqudit Entanglement Transformation,
M. Gharahi and V. Lysikov,
Quantum 8, 1238 (2024) - Homogeneous Algebraic Complexity Theory and Algebraic Formulas,
P. Dutta, F. Gesmundo, C. Ikenmeyer, G. Jindal, V. Lysikov,
Proceedings of the 15th Innovations in Theoretical Computer Science Conference (ITCS), 43:1–43:23 (2024) - Basic quantum subroutines: finding multiple marked elements and summing numbers,
J. van Apeldoorn, S. Gribling, H. Nieuwboer,
Quantum 8, 1284 (2024)
2023
- Thrifty shadow estimation: re-using quantum circuits and bounding tails,
J. Helsen and M. Walter,
Physical Review Letters 131 (2023), 240602;
also presented at TQC'23 - Public-Key Encryption with Quantum Keys,
K. Barooti, A.B. Grilo, L. Huguenin-Dumittan, G. Malavolta, O. Sattath, Q.-H. Vu, M. Walter,
Theory of Cryptography: 21st International Conference, Proceedings (TCC 2023) - Weakening Assumptions for Publicly-Verifiable Deletion,
J. Bartusek, D. Khurana, G. Malavolta, A. Poremba, M. Walter,
Theory of Cryptography: 21st International Conference, Proceedings (TCC 2023) - A simple construction of quantum public-key encryption from quantum-secure one-way functions,
K. Barooti, G. Malavolta, M. Walter,
arXiv:2303.01143 (subsumed by "Public-Key Encryption with Quantum Keys") - (No) Quantum ST tradeoff for USTCON,
S. Apers, S. Jeffery, G. Pass, M. Walter,
Proceedings of the 31st Annual European Symposium on Algorithms (ESA), 10:1-10:17 (2023) - Boundaries & Localisation with a Topological Twist,
S. Crew, D. Zhang, Boan Zhao,
Journal of High Energy Physics 2023 (93) - Quantum Regularized Least Squares,
S. Chakraborty, A. Morolia, A. Peduri,
Quantum 7, 988 (2023) - Quantum Brascamp-Lieb Dualities,
M. Berta, D. Sutter, M. Walter,
Communications in Mathematical Physics 401, 1807-1830 (2023) - Estimating gate-set properties from random sequences,
J. Helsen, M. Ioannou, I. Roth, J. Kitzinger, E. Onorati, A.H. Werner, J. Eisert,
Nature Comm. 14, 5039 (2023) - Fun with replicas: tripartitions in tensor networks and gravity,
G. Penington, M. Walter, F. Witteveen,
Journal of High Energy Physics 2023, 8 (2023) - Horn conditions for quiver subrepresentations and the moment map,
V. Baldoni, M. Vergne, M. Walter,
Pure and Applied Mathematics Quarterly 19 (4), 1687-1731 (2023) - Moment cone membership for quivers in strongly polynomial time,
M. Vergne, M. Walter,
arXiv:2303.14821 (note, not to be published) - A benchmarking procedure for quantum networks,
J. Helsen and S. Wehner,
npj Quantum Inf 9, 17 (2023) - Quantum Gravity in the Lab. II. Teleportation by Size and Traversable Wormholes,
S. Nezami, H. Lin, A. Brown, H. Gharibyan, S. Leichenauer, G. Salton, L. Susskind, B. Swingle, M. Walter,
PRX Quantum 4, 010321 (2023) - Quantum Gravity in the Lab. I. Teleportation by Size and Traversable Wormholes,
A. Brown, H. Gharibyan, S. Leichenauer, H. Lin, S. Nezami, G. Salton, L. Susskind, B. Swingle, M. Walter,
PRX Quantum 4, 010320 (2023);
also presented at TQC'21 - The minimal canonical form of a tensor network,
A. Acuaviva, V. Makam, H. Nieuwboer, D. Pérez-García, F. Sittner, M. Walter, F. Witteveen,
Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS) 328-362 (2023);
also presented at QIP'23 (short plenary talk)
2022
- A converse to Lieb-Robinson bounds in one dimension using index theory,
D. Ranard, M. Walter, F. Witteveen,
Annales Henri Poincaré 23 (309), 3905-3979 (2022);
also presented at QIP'21 - Maximum likelihood estimation for tensor normal models via castling transforms,
H. Derksen, V. Makam, M. Walter,
Forum of Mathematics, Sigma 10, E50 (2022) - Matchgate benchmarking: Scalable benchmarking of a continuous family of many-qubit gates,
J. Helsen, S. Nezami, M. Reagor, M. Walter,
Quantum 6, 657 (2022) - Quantum circuit approximations and entanglement renormalization for the Dirac field in 1+1 dimensions,
F. Witteveen, V. Scholz, B. Swingle, M. Walter,
Communications in Mathematical Physics 389, 75-120 (2022) - A general framework for randomized benchmarking,
J. Helsen, I. Roth, E. Onorati, A.H. Werner, J. Eisert,
PRX Quantum 3, 020357 (2022) - Improved quantum lower and upper bounds for matrix scaling,
S. Gribling and H. Nieuwboer,
Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS), 35:1-35:23 (2022)
2021
- Holographic entanglement negativity and replica symmetry breaking,
X.Dong, X.-L. Qi, M. Walter,
Journal of High Energy Physics 06 024 (2021) - Polynomial time algorithms in invariant theory for torus actions,
P. Bürgisser, M. L. Doğan, V. Makam, M. Walter, A. Wigderson,
Proceedings of the 36th Computational Complexity Conference (CCC), 32:1-32:30 (2021) - Quantum algorithms for matrix scaling and matrix balancing,
J. van Apeldoorn, S. Gribling, Y. Li, H. Nieuwboer, M. Walter, R. de Wolf,
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), 110:1-110:17 (2021);
also presented at TQC'21 - Bosonic entanglement renormalization circuits from wavelet theory,
F. Witteveen and M. Walter,
SciPost Phys. 10, 143 (2021) - Hypergraph min-cuts from quantum entropies,
M. Walter and F. Witteveen,
Journal of Mathematical Physics 62, 092203 (2021) (Editor's Pick) - Asymptotic performance of port-based teleportation,
M. Christandl, F. Leditzky, C. Majenz, G. Smith, F. Speelman, M. Walter,
Communications in Mathematical Physics 381, 379-451 (2021);
also presented at QIP'19 - Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations,
D. Gross, S. Nezami, M. Walter,
Communications in Mathematical Physics 385, 1325-1393 (2021);
also presented at QIP'18
2020
- Signal processing techniques for efficient compilation of controlled rotations in trapped ions,
K. Groenland, F. Witteveen, K. Schoutens, R. Gerritsma,
New Journal of Physics 22, 063006 (2020) - Witnessing Entanglement in Experiments with Correlated Noise,
B. Dirkse, M. Pompili, R. Hanson, M. Walter, S. Wehner,
Quantum Science and Technology 5, 035007 (2020) - Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings,
A. Garg, C. Ikenmeyer, V. Makam, R. Oliveira, M. Walter, A. Wigderson,
Proceedings of the 35th Computational Complexity Conference (CCC), 12:1-12:17 (2020) - A Quantum Multiparty Packing Lemma and the Relay Channel,
D. Ding, H. Gharibyan, P. Hayden, M. Walter,
IEEE Transactions on Information Theory 66, 3500-3519 (2020) - Bit Threads and Holographic Monogamy,
S. X. Cui, P. Hayden, T. He, M. Headrick, B. Stoica, M. Walter,
Communications in Mathematical Physics 376, 609-648 (2020) - Multipartite Entanglement in Stabilizer Tensor Networks,
S. Nezami and M. Walter,
Physical Review Letters 125 (2020), 241602
2019
- Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes,
P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter, A. Wigderson,
Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS), 845-861 (2019) - Entanglement Wedge Reconstruction via Universal Recovery Channels,
J. Cotler, P. Hayden, G. Penington, G. Salton, B. Swingle, M. Walter,
Physical Review X 9 (2019) 031011;
also presented at QIP'18 - Hyperpfaffians and Geometric Complexity Theory,
C. Ikenmeyer and M. Walter,
arXiv:1912.09389 (subsumed by "Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings") - Multi-partite entanglement,
M. Walter, J. Eisert, D. Gross,
invited book chapter of “Lectures on Quantum Information”, D. Bruss, G. Leuchs (eds.), second edition (2019)
2018
- Efficient algorithms for tensor scaling, quantum marginals and moment polytopes,
P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter, A. Wigderson,
Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS), 883-894 (2018) - Matrix product states and the quantum max-flow/min-cut conjectures,
F. Gesmundo, J.M. Landsberg, M. Walter,
Journal of Mathematical Physics 59 (2018) 102205 - Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory,
P. Bürgisser, A. Garg, R. Oliveira, M. Walter, A. Wigderson,
Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS), 24:1-24:20 (2018) - Rigorous free fermion entanglement renormalization from wavelet theory,
J. Haegeman, B. Swingle, M. Walter, J. Cotler, G. Evenbly, V.B. Scholz,
Physical Review X 8 (2018) 011003;
also presented at QIP'18 - Computation of Dilated Kronecker Coefficients, Appendix,
V. Baldoni, M. Vergne, M. Walter,
Journal of Symbolic Computation 84 (2018) - Horn inequalities and quivers,
V. Baldoni, M. Vergne, M. Walter,
arXiv:1804.00431 (announcement of "Horn conditions for quiver subrepresentations and the moment map") - Recoupling Coefficients and Quantum Entropies,
M. Christandl, M.B. Şahinoğlu, M. Walter,
Annales Henri Poincaré 19 (2), 385-410 (2018);
also presented at QIP'13
2017
- Entanglement from Topology in Chern-Simons Theory,
G. Salton, B. Swingle, M. Walter,
Physical Review D 95 (2017) 105007 - The Horn inequalities from a geometric point of view,
N. Berline, M. Vergne, M. Walter,
L'Enseignement Mathématique 63, 403-470 (2017) - Entanglement-assisted capacities of compound quantum channels,
M. Berta, H. Gharibyan, M. Walter,
IEEE Transactions on Information Theory 63 (5), 3306-3321 (2017) - Membership in moment polytopes is in NP and coNP,
P. Bürgisser, M. Christandl, K.D. Mulmuley, M. Walter,
SIAM Journal on Computing 46, 972-991 (2017) - On vanishing of Kronecker coefficients,
C. Ikenmeyer, K.D. Mulmuley, M. Walter,
Computational Complexity 26 (26), 949-992 (2017) - Inequalities for Moment Cones of Finite-Dimensional Representations,
M. Vergne and M. Walter,
Journal of Symplectic Geometry 15 (4), 1209 (2017)