quantum algorithms | Algorithms at UNSW

We study what speedups can and cannot be achieved in quantum models of computation.

Post-quantum cryptography studies cryptographic methods that are resistant against these speedups.

selected papers

ICALP

Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems

In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, 2024

DOI arXiv Bib

@inproceedings{GaspersL24,
  author = {Gaspers, Serge and Li, Jerry Zirui},
  editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  title = {Quantum Algorithms for Graph Coloring and Other Partitioning, Covering,
                    and Packing Problems},
  booktitle = {51st International Colloquium on Automata, Languages, and Programming,
                    {ICALP} 2024, July 8-12, 2024, Tallinn, Estonia},
  series = {LIPIcs},
  volume = {297},
  pages = {69:1--69:20},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2024},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2024.69},
  doi = {10.4230/LIPICS.ICALP.2024.69}
}

CRYPTO

Xinyu Zhang, Ron Steinfeld, Muhammed F. Esgin, Joseph K. Liu, Dongxi Liu, and Sushmita Ruj

Loquat: A SNARK-Friendly Post-quantum Signature Based on the Legendre PRF with Applications in Ring and Aggregate Signatures

In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part I, 2024

DOI preprint Bib

@inproceedings{ZhangSELLR24,
  author = {Zhang, Xinyu and Steinfeld, Ron and Esgin, Muhammed F. and Liu, Joseph K. and Liu, Dongxi and Ruj, Sushmita},
  editor = {Reyzin, Leonid and Stebila, Douglas},
  title = {Loquat: {A} SNARK-Friendly Post-quantum Signature Based on the Legendre
                    {PRF} with Applications in Ring and Aggregate Signatures},
  booktitle = {Advances in Cryptology - {CRYPTO} 2024 - 44th Annual International
                    Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024,
                    Proceedings, Part {I}},
  series = {Lecture Notes in Computer Science},
  volume = {14920},
  pages = {3--38},
  publisher = {Springer},
  year = {2024},
  url = {https://doi.org/10.1007/978-3-031-68376-3\_1},
  doi = {10.1007/978-3-031-68376-3\_1}
}

ICALP

Andrew M. Childs, Wim Dam, Shih-Han Hung, and Igor E. Shparlinski

Optimal Quantum Algorithm for Polynomial Interpolation

In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, 2016

DOI arXiv Bib

@inproceedings{ChildsDHS16,
  author = {Childs, Andrew M. and van Dam, Wim and Hung, Shih{-}Han and Shparlinski, Igor E.},
  editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  title = {Optimal Quantum Algorithm for Polynomial Interpolation},
  booktitle = {43rd International Colloquium on Automata, Languages, and Programming,
                    {ICALP} 2016, July 11-15, 2016, Rome, Italy},
  series = {LIPIcs},
  volume = {55},
  pages = {16:1--16:13},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2016},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2016.16},
  doi = {10.4230/LIPICS.ICALP.2016.16}
}