一句话：首次将 spooky pebble game 用于一般电路，证明量子空间上界与 PSPACE 完全性，并给出 SAT 求解器评估权衡。
Pebble game 用于研究空间/时间权衡；spooky pebble game 近期被提出，用于分析量子计算机模拟经典电路时经典空间、量子空间与时间的权衡。本文首次将该框架应用于一般电路，证明了该游戏中量子空间的上界，并证明求解该游戏是 PSPACE 完全的。作者还提出一个结合 SAT 求解器与启发式优化器的求解器，用于计算最优的经典空间/量子空间/时间权衡。实验表明，在有限运行时间内，该求解器能找到在考虑经典空间时降低量子空间的策略，说明该模型有助于减少量子空间。
Pebble games are used to study space/time trade-offs. Recently, spooky pebble games were introduced to study classical space / quantum space / time trade-offs for simulation of classical circuits on quantum computers. In this paper, the spooky pebble game framework is applied for the first time to general circuits. Using this framework we prove an upper bound for quantum space in the spooky pebble game. We also prove that solving the spooky pebble game is PSPACE-complete. Moreover, we present a solver for the spooky pebble game based on satisfiability solvers combined with heuristic optimizers. This spooky pebble game solver was empirically evaluated by calculating optimal classical space / quantum space / time trade-offs. Within limited runtime, the solver could find a strategy reducing quantum space when classical space is taken into account, showing that the spooky pebble model is useful to reduce quantum space.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2401-10579,
title = {Trade-offs between classical and quantum space using spooky pebbling},
author = {Arend-Jan Quist and Alfons Laarman},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 4},
year = {2025},
doi = {10.46298/lmcs-21(4:29)2025}
}