Group Publications

2024

• Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness,
  V. Lysikov, M. Walter,
  arXiv:2411.04639

• Algebraic metacomplexity and representation theory,
  M. van den Berg, P. Dutta, F. Gesmundo, C. Ikenmeyer, V. Lysikov
  arXiv:2411.03444

• The resource theory of tensor networks,
  M. Christandl, V. Lysikov, V. Steffan, A. H. Werner, F. Witteveen
  Quantum 8, 1560 (2024), QIP’24.

• Compiled Nonlocal Games from any Trapdoor Claw-Free Function,
  K. Bacho, A. Kulpe, G. Malavolta, S. Schmidt, M. Walter,
  eprint:2024/1829

• 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

• A bound on the quantum value of all compiled nonlocal games,
  A. Kulpe, G. Malavolta, C. Paddock, S. Schmidt, M. Walter
  arXiv:2408.06711, accepted at QIP’25.

• Permutation Superposition Oracles for Quantum Query Lower Bounds,
  C. Majenz, G. Malavolta, M. Walter,
  arXiv:2407.09655, accepted at QIP’25.

• 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,
  QIP’24 and accepted at CRYPTO’24.

• Exponential Quantum One-Wayness and EFI Pairs,
  G. Malavolta, T. Morimae, M. Walter, T. Yamakawa,
  arXiv:2404.13699; accepted at SCN’24.

• 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,
  arXiv:2402.17301; TQC’24.

• Partial Degeneration of Tensors,
  M. Christandl, F. Gesmundo, V. Lysikov, V. Steffan,
  SIAM J. Matrix Analysis Appl. 45 (1), 771–800 (2024)

• Fixed-parameter debordering of Waring rank,
  P. Dutta, F. Gesmundo, C. Ikenmeyer, G. Jindal, V. Lysikov,
  41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), 30:1–30:15.

• Persistent Tensors and Multiqudit Entanglement Transformation,
  M. Gharahi, V. Lysikov,
  Quantum 8, 1238 (2024).

• Homogeneous Algebraic Complexity Theory and Algebraic Formulas,
  P. Dutta, F. Gesmundo, C. Ikenmeyer, G. Jindal, V. Lysikov,
  15th Innovations in Theoretical Computer Science Conference (ITCS 2024), 43:1–43:23.

2023

• Graphs with quantum symmetry and trivial automorphism group,
  J. van Dobben de Bruyn, D. E. Roberson, S. Schmidt,
  arXiv:2311.04889.

• Quantum automorphism groups of trees,
  J. van Dobben de Bruyn, P. N. Kar, D. E. Roberson, S. Schmidt, P. Zeman,
  arXiv:2311.04891.

• 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,
  arXiv:2310.12662; QIP’24.

• Thrifty shadow estimation: re-using quantum circuits and bounding tails,
  J. Helsen, M. Walter,
  Physical Review Letters 131 (2023), 240602. TQC’23.

• Random tensor networks with nontrivial links,
  N. Cheng, C. Lancien, G. Penington, M. Walter, F. Witteveen,
  Annales Henri Poincaré (2023).

• 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).

• (No) Quantum ST tradeoff for USTCON,
  S. Apers, S. Jeffery, G. Pass, M. Walter,
  Proceedings of the 31st Annual European Symposium on Algorithms (ESA), LIPIcs, vol 274 (2023).

• QbC: Quantum Correctness by Construction,
  A. Peduri, I. Schaefer, M. Walter,
  arXiv:2307.15641; PLanQC’24.

• Boundaries & Localisation with a Topological Twist,
  S. Crew, Daniel Zhang, Boan Zhao,
  Journal of High Energy Physics 2023 (93).

• Quantum Regularized Least Squares,
  S. Chakraborty, A. Morolia, A. Peduri,
  Quantum 7, 988 (2023).

• Resurgence of Habiro elements,
  S. Crew, A. Goswami, R. Osburn,
  arXiv:2304.07001.

• Moment cone membership for quivers in strongly polynomial time,
  M. Vergne, M. Walter,
  arXiv:2303.14821.

• Exponential asymptotics and higher-order Stokes phenomenon in singularly perturbed ODEs,
  J. Shelton, S. Crew, Philippe H. Trinh,
  arXiv:2303.07866.

• Interior-point methods on manifolds: theory and applications,
  H. Hirai, H. Nieuwboer, M. Walter,
  to appear in Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS’23).

• A simple construction of quantum public-key encryption from quantum-secure one-way functions,
  K. Barooti, G. Malavolta, M. Walter,
  arXiv:2303.01143 (see also arXiv:2306.07698)

• Basic quantum subroutines: finding multiple marked elements and summing numbers,
  J. van Apeldoorn, S. Gribling, H. Nieuwboer,
  arXiv:2302.10244.

• Quantum Brascamp-Lieb Dualities,
  M. Berta, D. Sutter, M. Walter,
  Communications in Mathematical Physics 401 (2023), 1807–1830.

• Fun with replicas: tripartitions in tensor networks and gravity,
  G. Penington, M. Walter, F. Witteveen,
  Journal of High Energy Physics 2023, 8 (2023).

• Quantum Gravity in the Lab: Teleportation by Size and Traversable Wormholes, Part II,
  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: 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); TQC’21.

• 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).

2022

• 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,
  to appear in Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS’23); QIP’23 (short plenary talk).

• 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); QIP’21.

• Maximum likelihood estimation for tensor normal models via castling transforms,
  H. Derksen, V. Makam, M. Walter,
  Forum of Mathematics, Sigma 10 (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).

2021

• Estimating gate-set properties from random sequences,
  J. Helsen, M. Ioannou, I. Roth, J. Kitzinger, E. Onorati, A.H. Werner, J. Eisert,
  arXiv:2110.13178.

• Near optimal sample complexity for matrix and tensor normal models via geodesic convexity,
  C. Franks, R. Oliveira, A. Ramachandran, M. Walter,
  arXiv:2110.07583.

• Improved quantum lower and upper bounds for matrix scaling,
  S. Gribling and H. Nieuwboer,
  39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022).

• 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 4/9 (CCC), 32:1-32:30 (2021).

• Holographic entanglement negativity and replica symmetry breaking,
  X.Dong, X.-L. Qi, M. Walter,
  Journal of High Energy Physics 06 024 (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); 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); 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 (2021), 1325–1393; QIP’18.

• A benchmarking procedure for quantum networks,
  J. Helsen and S. Wehner,
  arXiv:2103.01165.

2020

• A general framework for randomized benchmarking,
  J. Helsen, I. Roth, E. Onorati, A.H. Werner, J. Eisert,
  arXiv:2010.07974.

• 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 (2020).

• 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.

• 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, M. Walter,
  Physical Review Letters 125 (2020), 241602.

2019

• Hyperpfaffians and Geometric Complexity Theory,
  C. Ikenmeyer, M. Walter,
  arXiv:1912.09389.

• 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; QIP’18.

• 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).

• Horn inequalities and quivers,
  V. Baldoni, M. Vergne, M. Walter,
  arXiv:1804.00431.

• 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 2018), 24:1–24:20.

• 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; QIP’18.

• Computation of Dilated Kronecker Coefficients, Appendix,
  V. Baldoni, M. Vergne, M. Walter,
  Journal of Symbolic Computation 84 (2018).

• Recoupling Coefficients and Quantum Entropies,
  M. Christandl, M.B. Şahinoğlu, M. Walter,
  Annales Henri Poincaré 19 (2), 385-410 (2018); QIP’13.

2017

• The Horn inequalities from a geometric point of view,
  N. Berline, M. Vergne, M. Walter,
  L’Enseignement Mathématique 63, 403-470 (2017).

• Entanglement from Topology in Chern-Simons Theory,
  G. Salton, B. Swingle, M. Walter,
  Physical Review D 95 (2017) 105007.

• 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 (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).

Group members highlighted in bold.