量子科技中心_量科网

空间复杂度是理论计算机科学的关键研究领域。在量子计算背景下，理解空间受限计算能力尤为重要，因为量子比特是一种极其珍贵且有限的资源。近期出现的“催化计算”这一空间受限复杂性新分支表明，空间复用是一种非常强大的计算资源，尤其适用于空间开销极小的子程序。虽然信息论背景下的量子催化作用以及“脏”量子比特对量子计算的价值已被研究多年，但这些模型通常不适用于量子空间受限算法——它们要么依赖特定催化状态，要么会破坏所借用的内存。 该研究团队定义了量子背景下的催化计算概念，并展示了关于该模型的若干初步研究成果。首先，该工作证明量子催化对数空间问题始终能在多项式时间内完成量子计算，而这一结论的经典对应正是催化计算领域最大的开放性问题。这使得量子催化空间可以用电路而非图灵机的方式等价定义。研究人员还证实，量子催化对数空间能模拟对数深度阈值电路（已知该类电路包含且可能严格包含量子对数空间），从而彰显了量子催化空间的强大能力。最后，该团队证明单量子比特清洁模型可同时模拟酉量子催化对数空间和经典催化对数空间。