Stacey Jeffery

Bio

I've been a Senior Researcher at CWI since January 2017, where I'm a member of QuSoft, and since October 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 inaugural lecture can be found here (text) and here (video). 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), supervised by Michele Mosca, and informally co-advised by Frédéric Magniez.

• 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. Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer
   S. Jeffery and G. Pass (2024). arXiv:2401.08355
2. Taming Quantum Time Complexity
   A. Belovs, S. Jeffery and D. Yolcu (2023). arXiv:2311.15873
3. 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.
4. (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.
5. Quantum Subroutine Composition
   S. Jeffery (2022). arXiv:2209.14146
   • Presented at the 26^th Annual Conference on Quantum Information Processing (QIP 2023).
6. 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).
7. 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).
8. 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.
9. 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.
10. 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).
11. 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).
12. 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).
13. 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).
14. 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).
15. 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.
16. 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.
17. 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.
18. 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).
19. 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).
20. 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).
21. 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).
22. 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).
23. 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).
24. 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).
25. 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.
26. 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.
27. 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.
28. 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.
29. 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.
30. 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]
31. 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