Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
复制标题
使用经典量子混合内存进行学习的内存样本下限
DOI：
10.1145/3564246.3585129
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Zhan, Wei
中科院分区：
文献类型：
--
作者：
Liu, Qipeng;Raz, Ran;Zhan, Wei
在Raz（J. ACM and FOCS 16）的一项工作中，证明了任何在nbits上进行奇偶校验学习的算法要么需要Ω（n2）位的经典存储器，要么需要一个指数数量的随机样本。 最近的一系列工作继续了这一研究方向，并表明对于大量的经典学习任务，需要超线性的经典记忆大小或超多项式的许多样本。所有这些工作都把学习算法看作是经典的分支程序，在有限的内存中执行经典的计算。 然而，这些结果并没有捕捉到所有的物理计算模型，特别是量子计算机和量子存储器的使用。它留下了一种可能性，即一小块量子记忆可以显著减少对经典记忆或样本的需求，从而完全改变经典学习任务的性质。尽管最近的研究表明，量子记忆对于阴影断层扫描和纯度测试等内在量子学习问题的必要性，但量子记忆在经典学习任务中的作用仍然模糊不清。 在这项工作中，我们研究了量子记忆存在下的经典学习任务。我们证明了任何同时具有经典记忆和量子记忆的量子算法，对于nbits的奇偶校验学习，需要Ω（n2）比特的经典记忆或Ω（n）比特的量子记忆或指数数量的样本。换句话说，奇偶学习的记忆样本下限在性质上保持不变，即使学习算法除了使用经典记忆外，还可以使用大小为0的量子记忆（对于某些常数>0）。 我们的结果是更普遍的，适用于许多其他经典的学习任务。继之前的工作之后，我们用矩阵M表示：A×X→ {-1，1}以下学习任务。一个未知数是从一个概念类X中随机均匀采样的，一个学习算法试图通过观察随机样本流（ai，bi=M（ai，x））来发现x，其中对于每个i，ai∈ A是随机均匀选择的。假设k，n，n是稀有整数，使得M的任何子矩阵至少为2-k·|一|行和至少2− 1·|X|列，具有至多2−r的偏差。我们证明了，任何具有经典和量子混合记忆的学习问题的算法对应于M需要（1）Ω（k·k）比特的经典记忆，或（2）Ω（r）量子记忆，或（3）2Ω（r）随机样本，以实现成功概率至少为2−O（r）。 我们的研究结果反驳了少量量子存储器显着减少有效学习这些问题所需的经典存储器大小的可能性。我们的研究结果还表明，在有界存储模型（协议是基于奇偶校验学习onnbits）的几个现有的密码协议的安全性提高，证明安全性举行，即使在存在的量子对手最多cn2 bits的经典记忆和cnbits的量子记忆（对于某些常数>0）。
In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning onnbits requires either Ω(n2) bits of classical memory or an exponential number (in n) of random samples. A line of recent works continued that research direction and showed that for a large collection of classical learning tasks, either super-linear classical memory size or super-polynomially many samples are needed. All these works consider learning algorithms as classical branching programs, which perform classical computation within bounded memory. However, these results do not capture all physical computational models, remarkably, quantum computers and the use of quantum memory. It leaves the possibility that a small piece of quantum memory could significantly reduce the need for classical memory or samples and thus completely change the nature of the classical learning task. Despite the recent research on the necessity of quantum memory for intrinsic quantum learning problems like shadow tomography and purity testing, the role of quantum memory in classical learning tasks remains obscure. In this work, we study classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning onnbits, requires either Ω(n2) bits of classical memory or Ω(n) bits of quantum memory or an exponential number of samples. In other words, the memory-sample lower bound for parity learning remains qualitatively the same, even if the learning algorithm can use, in addition to the classical memory, a quantum memory of sizecn(for some constantc>0). Our result is more general and applies to many other classical learning tasks. Following previous works, we represent by the matrixM:A×X→ {−1,1} the following learning task. An unknownxis sampled uniformly at random from a concept classX, and a learning algorithm tries to uncoverxby seeing streaming of random samples (ai,bi=M(ai,x)) where for everyi,ai∈Ais chosen uniformly at random. Assume thatk,ℓ,rare integers such that any submatrix ofMof at least 2−k·|A| rows and at least 2−ℓ·|X| columns, has a bias of at most 2−r. We prove that any algorithm with classical and quantum hybrid memory for the learning problem corresponding toMneeds either (1) Ω(k· ℓ) bits of classical memory, or (2) Ω(r) qubits of quantum memory, or (3) 2Ω(r)random samples, to achieve a success probability at least 2−O(r). Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems. Our results also imply improved security of several existing cryptographical protocols in the bounded-storage model (protocols that are based on parity learning onnbits), proving that security holds even in the presence of a quantum adversary with at mostcn2bits of classical memory andcnbits of quantum memory (for some constantc>0).
登录
查看更多内容
有界存储模型中的安全多方计算
DOI：
10.1007/978-3-030-92641-0_14
发表时间：
2021
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Jiahui Liu;Satyanarayana Vusirikala
通讯作者：
Satyanarayana Vusirikala
论混合有界存储模型中的永久安全
DOI：
--
发表时间：
2006
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Danny Harnik;M. Naor
通讯作者：
M. Naor
说得多，记住少：重新审视有界存储模型中的密码学
DOI：
10.1007/978-3-031-30545-0_4
发表时间：
2021
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Y. Dodis;Willy Quach;Daniel Wichs
通讯作者：
Daniel Wichs
有限存储模型中的身份验证
DOI：
10.1007/978-3-031-07082-2_26
发表时间：
2022
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
Y. Dodis;Willy Quach;Daniel Wichs
通讯作者：
Daniel Wichs
DOI：
10.4230/lipics.itcs.2018.28
发表时间：
2018
期刊：
--
影响因子：
--
作者：
Dana Moshkovitz;Michal Moshkovitz
通讯作者：
Dana Moshkovitz;Michal Moshkovitz