Stacey Jeffery

Bio

I've been a Senior Researcher at CWI since 2017, where I'm a member of QuSoft, and since 2023, I've held a special appointment as Professor of Quantum Information at the Korteweg-de Vries Institute for Mathematics at the University of Amsterdam. My research is mainly on quantum algorithms and models of quantum computation.

Previously, I was an IQIM Postdoctoral Fellow at the Institute for Quantum Information and Matter (IQIM) at Caltech. I received my PhD from the University of Waterloo in 2014, where I was affiliated with the Institute for Quantum Computing (IQC). .

• Check out my guest complexity column in the December 2024 issue of ACM SIGACT News (arXiv version here)
• I currently hold an ERC Starting Grant
• I was co-chair of the QIP 2022 program committee
• With Julia Cramer, I co-founded WIQD (Women in Quantum Development), a professional network for women in all areas of quantum technology, for which we were awarded the first QDNL Award
• I have served on the steering committees of QCrypt and TQC (in 2021 I was chair)
• I am Chair of the Lorentz Center Informatics Advisory board
• I am a CIFAR Fellow in the Quantum Information Science Program

Publications and Preprints

1. Space-Efficient Quantum Error Reduction without log Factors
   A. Belovs and S. Jeffery (2025). arXiv:2502.09249
2. Composing Quantum Algorithms
   S. Jeffery (2024). arXiv:2502.09240
   • SIGACT News Complexity Column 123, December 2024 issue of ACM SIGACT News.
3. Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer
   S. Jeffery and G. Pass (2024). arXiv:2401.08355
   • To appear in Proceedings of STACS 2025.
4. Taming Quantum Time Complexity
   A. Belovs, S. Jeffery and D. Yolcu (2023). arXiv:2311.15873
   • Quantum 8, 1444 (2024).
5. Quantum Algorithm for Path-Edge Sampling
   S. Jeffery, S. Kimmel and A. Piedrafita (2023). arXiv:2303.03319
   • Proceedings of the 18^th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Pages 5:1 – 5:28.
6. (No) Quantum space-time tradeoff for USTCON
   S. Apers, S. Jeffery, G. Pass and M. Walter (2022). arXiv:2212.00094
   • Proceedings of the 31^st Annual European Symposium on Algorithms (ESA 2023). Pages 10:1 – 10:17.
7. Quantum Subroutine Composition
   S. Jeffery (2022). arXiv:2209.14146
   • Presented at the 26^th Annual Conference on Quantum Information Processing (QIP 2023).
   • To apper in Theory of Computing.
8. Multidimensional Quantum Walks, with Application to k-Distinctness
   S. Jeffery and S. Zur (2022). arXiv:2208.13492
   • Proceedings of the 55^th Annual ACM Symposium on Theory of Computing (STOC 2023). Pages 1125 – 1130.
   • Presented as a short plenary at the 26^th Annual Conference on Quantum Information Processing (QIP 2023).
   • To apper in TheoretiCS.
9. Secure software leasing without assumptions
   A. Broadbent, S. Jeffery, S. Lord, S. Podder and A. Sundaram (2021). arXiv:2101.12739
   • Proceedings of the 19^th International Conference on the Theory of Cryptography (TCC 2021). Pages 90 – 120.
   • Presented at the 24^th Annual Conference on Quantum Information Processing (QIP 2021).
   • Presented as an Invited Talk at the 21^st Asian Quantum Information Science Conference (AQIS 2021).
10. Span programs and quantum time complexity
    A. Cornelissen, S. Jeffery, M. Ozols and A. Piedrafita (2020). arXiv:2005.01323
    • Proceedings of the 45^th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Pages 26:1 – 26:14.
11. A Unified Framework of Quantum Walk Search
    S. Apers, A. Gilyén and S. Jeffery (2019). arXiv:1912.04233
    • Proceedings of the 38^th Symposium on Theoretical Aspects of Computer Science (STACS 2020). Pages 6:1 – 6:13.
12. Secure Multi-party Quantum Computation with a Dishonest Majority
    Y. Dulek, A. B. Grilo, S. Jeffery, C. Majenz and C. Schaffner (2019). arXiv:1909.13770
    • Advances in Cryptology: Proceedings of the 39^th Annual International Conference on the Theory and Applications of Cryptographic Techniqes (Eurocrypt 2020). Pages 729 – 758.
    • Presented at the 10^th International Conference on Quantum Cryptography (QCrypt 2020).
13. Span Programs and Quantum Space Complexity
    S. Jeffery (2019). arXiv:1908.04232
    • Proceedings of the 11^th Innovations in Theoretical Computer Science Conference (ITCS 2020). Pages 4:1 – 4:37.
    • Theory of Computing 18 (11), Pages 1 – 49 (2022).
14. Quadratic speedup for finding marked vertices by quantum walks
    A. Ambainis, A. Gilyén, S. Jeffery, and M. Kokainis (2019). arXiv:1903.07493
    • Proceedings of the 52^nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020). Pages 412 – 424.
    • Presented as a short plenary at the 23^rd Annual Conference on Quantum Information Processing (QIP 2020).
15. Experimental Demonstration of Quantum Fully Homomorphic Encryption with Application in a Two-Party Secure Protocol
    W. K. Tham, H. Ferretti, K. Bonsma-Fisher, A. Brodutch, B. C. Sanders, A. M. Steinberg, and S. Jeffery (2018). arXiv:1811.02149
    • Physical Review X 10, 011038 (2020).
16. On non-adaptive quantum chosenciphertext attacks and Learning with Errors
    G. Alagic, S. Jeffery, M. Ozols and A. Poremba (2018). arXiv:1808.09655
    • Proceedings of 14^th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Pages 1:1 – 1:23.
    • Presented at the 8^th International Conference on Quantum Cryptography (QCrypt 2018).
17. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
    S. Chakraborty, A. Gilyén and S. Jeffery (2018). arXiv:1804.01973
    • Proceedings of the 46^th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Pages 33:1 – 33:14.
18. Quantum Algorithms for Connectivity and Related Problems
    M. Jarret, S. Jeffery, S. Kimmel and A. Piedrafita (2018). arXiv:1804.10591
    • Proceedings of the 26^th Annual European Symposium on Algorithms (ESA 2018). Pages 49:1 – 49:13.
19. Attacks on the AJPS Mersenne-based cryptosystem
    K. de Boer, L. Ducas, S. Jeffery and R. de Wolf (2017). eprint 2017/1171
    • Proceedings of the 9^th International Conference on Post-Quantum Cryptography (PQCrypto 2018). Pages 101 – 120.
20. Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources
    A. Coladangelo, A. B. Grilo, S. Jeffery and T. Vidick (2017). arXiv:1708.07359
    • Advances in Cryptology: Proceedings of the 38^th Annual International Conference on the Theory and Applications of Cryptographic Techniqes (Eurocrypt 2019). Pages 247 – 277. .
    • Presented at the 21^st Conference on Quantum Information Processing (QIP 2018).
    • Presented as an Invited Talk at the 8^th International Conference on Quantum Cryptography (QCrypt 2018).
    • Theory of Computing 20 (3), Pages 1 – 87 (2024).
21. Quantum Algorithms for Graph Connectivity and Formula Evaluation
    S. Jeffery and S. Kimmel (2017). arXiv:1704.00765 (Subsumes arXiv:1511.02235)
    • Quantum 1, 26 (2017).
    • Presented at the 11^th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016).
22. Quantum Communication Complexity of Distributed Set Joins
    S. Jeffery and F. Le Gall (2016). arXiv:1608.06617
    • Proceedings of the 41^st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016).
    • Presented at the 11^th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016).
23. Approximate Span Programs
    T. Ito and S. Jeffery (2015). arXiv:1507.00432
    • Proceedings of the 43^rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
    • Algorithmica 81 (6), Pages 2158 – 2195 (2019).
24. Quantum homomorphic encryption for circuits of low T-gate complexity
    A. Broadbent and S. Jeffery (2014). arXiv:1412.8766
    • Advances in Cryptology: Proceedings of the 35^th Annual Cryptology Conference (CRYPTO 2015). Pages 609 – 629.
    • Presented at the 5^th International Conference on Quantum Cryptography (QCrypt 2015).
    • Presented at the 19^th Conference on Quantum Information Processing (QIP 2016).
25. Optimal parallel quantum query algorithms
    S. Jeffery, F. Magniez and R. de Wolf (2013). arXiv:1309.6116
    • Proceedings of the 22^nd European Symposium on Algorithms (ESA 2014). Pages 592 – 604.
    • Algorithmica 79 (2), Pages 409 – 529 (2017).
26. A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
    A. M. Childs, S. Jeffery, R. Kothari and F. Magniez (2013). arXiv:1302.7316
    • Merged with arXiv:1302.3143: A. Belovs, A. M. Childs, S. Jeffery, R. Kothari and F. Magniez (2013). Time-efficient quantum walks for 3-distinctness. Proceedings of the 40^th International Colloquium on Automata, Languages and Programming (ICALP 2013). Pages 105 – 122.
    • Presented at the 17^th Conference on Quantum Information Processing (QIP 2014).
27. Quantum Algorithms for the Subset-Sum Problem
    D. J. Bernstein, S. Jeffery, T. Lange and A. Meurer. (2013). ePrint
    • Proceedings of the 5^th International Conference on Post-Quantum Cryptography (PQCrypto 2013). Pages 16 – 33.
28. Partial-indistinguishability obfuscation using braids
    G. Alagic, S. Jeffery and S. Jordan (2012). arXiv:1212.6458
    • Proceedings of the 9^th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Pages 141 – 160.
29. Nested Quantum Walks with Quantum Data Structures
    S. Jeffery, R. Kothari and F. Magniez (2012). arXiv:1210.1199
    • Proceedings of the 24^th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013). Pages 1474 – 1485.
30. Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
    • S. Jeffery, R. Kothari and F. Magniez (2012). arXiv:1112.5855v2 Proceedings of the 39^th International Colloquium on Automata, Languages and Programming (ICALP 2012). Pages 522 – 532.
    • S. Jeffery, R. Kothari, F. Le Gall and F. Magniez (2015). Algorithmica 76 (1), Pages 1 – 16.
31. Trading Robustness for Correctness and Privacy in Certain Multiparty Computations, Beyond an Honest Majority
    A. Broadbent, S. Jeffery, S. Ranellucci and A. Tapp (2012).
    • Proceedings of the 6^th International Conference on Information Theoretic Security (ICITS 2012). Pages 14 – 36.
32. Exact, Efficient and Information-Theoretically Secure Voting with an Arbitrary Number of Cheaters
    A. Broadbent, S. Jeffery and A. Tapp (2010). arXiv:1011.5242[cs.CR]
33. HASS: A Scheduler for Heterogeneous Multicore Systems
    D. Shelepov, J. Saez, S. Jeffery, A. Fedorova, N. Perez, Z. Huang, S. Blagodurov and V. Kumar (2009).
    • Operating Systems Review (Special Issue on Interaction among the OS, Compilers, and Multicore Processors). 43(2):66 – 75.

Doctoral Thesis

• S. Jeffery (2014). Frameworks for Quantum Algorithms. Doctoral thesis, University of Waterloo. pdf

Masters Thesis

• S. Jeffery (2011). Collision Finding with Many Classical or Quantum Processors. Masters thesis, University of Waterloo. pdf

Other

• A musical collaboration with Maris Ozols