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.