量子数据下可高效检测布尔函数的单调性等性质
Testing classical properties from quantum data
- 用量子态副本而非经典采样进行性质测试
- 在单调性、对称性等测试中实现量子加速
- 适合研究量子复杂性与量子学习理论者
布尔函数的性质通常可以比学习函数本身更快地被测试。然而，当测试器仅能获取函数的随机样本（数据科学中的自然设定）时，这种优势通常消失。本文首次研究了量子版本的“数据科学场景”：仅从函数态 $|f angle /propto \ sum_x |x,f(x)\rangle$ 的副本中测试性质的量子算法。针对单调性、对称性和无三角形性三个经典性质，我们证明量子算法能恢复经典采样测试中丢失的速度优势。我们的新测试方法超越了量子傅里叶采样，且证明了仅依赖傅里叶采样和经典样本无法实现对称性常数复杂度测试。此外，我们发现存在一个问题，只需 $O(1)$ 个经典查询即可解决，却需要 $Ω(2^{n/2})$ 个函数态副本，表明量子数据与经典查询是“最大化不可比较”的资源。最后，我们初步探索了量子数据测试的下界问题，发现经典中已知的指数下界构造对量子数据不适用，需发展新工具。
原文摘要 · Abstract (English)
Properties of Boolean functions can often be tested much faster than the functions can be learned. However, this advantage usually disappears when testers are limited to random samples of a function $f$--a natural setting for data science--rather than queries. In this work we initiate the study of a quantum version of this "data science scenario": quantum algorithms that test properties of $f$ solely from quantum data in the form of copies of the function state $|f\rangle \propto \sum_x|x,f(x)\rangle$. $\bullet$ New tests. For three well-established properties--monotonicity, symmetry, and triangle-freeness--we show that the speedup lost when restricting classical testers to sampled data can be recovered by quantum algorithms operating solely from quantum data. $\bullet$ Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and we show that this necessary. In particular, there is no constant-complexity tester for symmetry relying solely on Fourier sampling and random classical samples. $\bullet$ Classical queries vs. quantum data. We exhibit a testing problem that can be solved from $O(1)$ classical queries but that requires $Ω(2^{n/2})$ function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. $\bullet$ Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of Goldreich et al. (2000) and Black (2023), which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。