第7章：计算能力与资源估计

复杂度类别

BQP 描述可由统一生成的多项式规模量子电路以有界错误概率判定的问题。统一性要求电路可有效生成，避免把不可计算答案直接藏进每个输入长度的电路描述。

Grover 给某些无结构搜索平方根级加速，Shor 对特定数论问题给出多项式时间算法；这不证明所有 NP 问题都能被量子计算高效解决。量子与经典复杂度类的许多包含关系仍未解决。

估计某事件概率到加性误差 $\epsilon$ ，朴素独立采样通常需要 $O(1/\epsilon^2)$ 量级样本才能达到固定成功概率。更强量子估计算法有不同资源要求，但依赖可控态制备和相干调用等额外能力。

最终只需一个决策 bit，与需要输出一个巨大向量，是不同任务。声称加速时应保持输入表示、输出要求和精度一致。

一项实际算法需要记录逻辑比特、门数、深度、连接要求、非 Clifford 门成本、纠错开销和采样次数。电路深度相同也可能因门种类与硬件不同而运行时间不同。

噪声设备上的误差缓解通过额外采样和统计校正改善某些估计，与容错纠错提供的可扩展逻辑保护不同。误差缓解成本可能随规模迅速上升。

变分算法用经典优化器调节参数化量子电路，测量目标期望。它结合量子态制备与经典优化，但目标通常非凸，还受到测量噪声、梯度变小和噪声影响。

一个小规模实例比某个简单经典程序快，不能直接证明渐近或实用优势。需要比较有竞争力的经典方法、计入训练与采样预算，并报告相同误差要求下的结果。