Quantum computation: through the algorithm and complexity theory lens

本计画旨在透过演算法与复杂性理论的透镜来增进我们对量子计算的了解。三个核心领域的理论将被检查：交互式计算模型，查询复杂性和电路下界。预期成果包括：揭示交互式计算模型的量子优势;在云中验证量子设备的技术和一般的量子云计算;锐化量子和经典查询模型中算法性能之间的分离;为量子电路建立无条件和条件硬度结果。这种全面的理解将增强澳大利亚在量子计算理论方面的研究组合。

This project aims to advance our knowledge of quantum computation through the lens of algorithm and complexity theory. Three core areas of the theory will be examined: interactive computing models, query complexity, and circuit lower bounds. The expected outcomes include: revealing the quantum advantages of interactive computing models; techniques for verifying quantum devices in the cloud and quantum cloud computing in general; sharpening the separation between algorithm performance in quantum and classical query models; establishing both unconditional and conditional hardness results for quantum circuits. This comprehensive understanding will enhance Australia's research portfolio in the theory of quantum computing.