PhD Scholarship: Quantum algorithms for exact exponential-time combinatorial optimisation | University of Technology Sydney
Summarize this article with:
PhD Scholarship: Quantum algorithms for exact exponential-time combinatorial optimisation | University of Technology Sydney Application deadline: Tuesday, May 12, 2026Employer web page: Sydney Quantum Academy Job type: PhDTransform your research into real-world impact with a PhD program co-designed with leading quantum experts and industry partners - open to domestic and international students. This project investigates exact quantum algorithms for NP-hard combinatorial optimisation problems, with the goal of improving the worst-case exponential running time. A representative target is Maximum Independent Set: given a graph G n vertices, find the largest set of vertices with no edges between them. The best published classical algorithm for Maximum Independent Set runs in time 1.1996^n (up to polynomial factors), while the best published quantum algorithm achieves expected running time proportional to 1.1488^n, which is an improvement in the base of the exponential base but still far from the kind of square-root quantum speedups seen in unstructured search. A major open direction is whether one can obtain a super-quadratic quantum speedup for exact, worst-case Maximum Independent Set, or for closely related problems such as Minimum Vertex Cover. The project will explore new quantum algorithmic ideas and analyses–e.g., quantum-accelerated branching/backtracking and or quantum divide and conquer–to push the best known worst-case bounds. Project Supervisor: Associate Professor Troy Lee, Centre for Quantum Software and Information, University of Technology Sydney Industry placement with Defence Science and Technology Group (DSTG) This project would suit: Students with a strong background in mathematics and/or theoretical computer science, prior quantum computing knowledge is welcome but not required. The research will be conducted in collaboration with the Australia Defence Science and Technology Group. Due to project requirements, the position is open only to citizens of AUKUS countries (Australia, United Kingdom, United States) This project is part of the ARC Training Centre Future Leaders in Quantum Computing Program (FLiQC). These scholarships are funded and delivered by FLiQC in partnership with Sydney Quantum Academy. The ARC Training Centre for Future Leaders in Quantum Computing (FLiQC) scholarship offers an industry PhD program which includes: A stipend worth A$42,754 p.a. (2026 rate, indexed annually) for a period of up to 4 years A research project co-designed with FLiQC industry partner(s) Substantive engagement with our industry partners as a core component of the PhD Access to an industry-ready skills training program provided by the ARC Training Centre Entry to the SQA PhD Experience Program events and workshops. Log in or register to post comments