计算复杂性
查看 最近的 文章
显示 2025年08月05日， 星期二 新的列表
- [1] arXiv:2508.01649 [中文pdf, pdf, html, 其他]
-
标题： 迈向EXPTIME单向函数：布隆过滤器、简洁图、团与自屏蔽标题： Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking评论： 先前版本见 https://eccc.weizmann.ac.il/report/2025/043/ 提交到arxiv作为提交到《Theory of Computing》的要求主题： 计算复杂性 (cs.CC) ; 密码学与安全 (cs.CR) ; 数据结构与算法 (cs.DS)
考虑具有n个节点的图，并使用长度为2 log3 n位的布隆过滤器。节点i和j之间的边（i < j）根据i和j的哈希函数开启布隆过滤器中的某个位。选择log n个节点，并开启所有使这些log n个节点形成团所需的布隆过滤器中的位。因此，布隆过滤器暗示了某些其他边的存在，即那些边(x, y)，其中x < y，使得对x和y应用哈希函数所选择的所有位恰好由于将团边哈希到布隆过滤器中而被开启。由团选择的边和映射到布隆过滤器中被开启位的边构成的图可以在n的多项式时间内构造。选择一个足够大的关于n的多项对数长度的布隆过滤器，可以保证该图只有一个大小为log n的团，即植入的团。当哈希函数是黑箱时，找到该团是困难的，因此将log n个节点映射到图的函数在多项式时间内无法（很可能无法）逆向。
Consider graphs of n nodes, and use a Bloom filter of length 2 log3 n bits. An edge between nodes i and j, with i < j, turns on a certain bit of the Bloom filter according to a hash function on i and j. Pick a set of log n nodes and turn on all the bits of the Bloom filter required for these log n nodes to form a clique. As a result, the Bloom filter implies the existence of certain other edges, those edges (x, y), with x < y, such that all the bits selected by applying the hash functions to x and y happen to have been turned on due to hashing the clique edges into the Bloom filter. Constructing the graph consisting of the clique-selected edges and those edges mapped to the turned-on bits of the Bloom filter can be performed in polynomial time in n. Choosing a large enough polylogarithmic in n Bloom filter yields that the graph has only one clique of size log n, the planted clique. When the hash function is black-boxed, finding that clique is intractable and, therefore, inverting the function that maps log n nodes to a graph is not (likely to be) possible in polynomial time.
新提交 (展示 1 之 1 条目 )
- [2] arXiv:2508.00983 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]
-
标题： 高斯玻色子采样中的隐藏猜想证明标题： Proof of Hiding Conjecture in Gaussian Boson Sampling评论： 21页，4图主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC) ; 数学物理 (math-ph)
高斯玻色取样（GBS）是一种展示量子计算优势的有前途的协议。证明GBS的经典困难性的一个关键步骤是所谓的“隐藏猜想”，该猜想断言可以将一个复数高斯矩阵作为外积的子矩阵，在总变分距离中“隐藏”在海拉酉子矩阵的外积中。在本文中，我们证明了输入状态具有最大数量压缩态的情况下的隐藏猜想，这是一个最近已在实验上实现的设置[Madsen等人，Nature 606, 75 (2022)]。在这种情况下，隐藏猜想指出，一个$o(\sqrt{M})\times o(\sqrt{M})$的子矩阵的$M\times M$圆正交系综（COE）随机矩阵可以在总变分距离中被一个复数高斯矩阵很好地近似，当$M\to\infty$时。这是在实验相关范围内对GBS隐藏性质的首次严格证明，并将用最大数量压缩态经典模拟GBS的困难性论证提升到与[Aaronson和Arkhipov，Theory Comput. 9, 143 (2013)]中传统玻色取样的困难性论证相当的水平。
Gaussian boson sampling (GBS) is a promising protocol for demonstrating quantum computational advantage. One of the key steps for proving classical hardness of GBS is the so-called ``hiding conjecture'', which asserts that one can ``hide'' a complex Gaussian matrix as a submatrix of the outer product of Haar unitary submatrices in total variation distance. In this paper, we prove the hiding conjecture for input states with the maximal number of squeezed states, which is a setup that has recently been realized experimentally [Madsen et al., Nature 606, 75 (2022)]. In this setting, the hiding conjecture states that a $o(\sqrt{M})\times o(\sqrt{M})$ submatrix of an $M\times M$ circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex Gaussian matrix in total variation distance as $M\to\infty$. This is the first rigorous proof of the hiding property for GBS in the experimentally relevant regime, and puts the argument for hardness of classically simulating GBS with a maximal number of squeezed states on a comparable level to that of the conventional boson sampling of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)].
- [3] arXiv:2508.02514 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]
-
标题： Forrelation 是极端困难的标题： Forrelation is Extremally Hard评论： 被接受为TQC 2025的演讲主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC)
对于关系问题是一个中心问题，它展示了量子和经典能力之间的指数分离。 在此问题中，给定对$n$位布尔函数$f$和$g$的查询访问权限，目标是估计对于关系函数$\mathrm{forr}(f,g)$，该函数衡量$g$与$f$的傅里叶变换之间的相关性。 在此工作中，我们提供了一个新的线性代数视角来研究对于关系问题，而不是之前分析方法。 我们将Forrelation问题与bent布尔函数建立了联系，并通过这一联系，分析了Forrelation问题的一个极值版本，其中目标是区分Forrelation的极值实例，即$(f,g)$与$\mathrm{forr}(f,g)=1$和$\mathrm{forr}(f,g)=-1$。 我们证明，这个问题可以通过一次量子查询以成功概率一解决，而即使对于有三分之一失败概率的算法，也需要$\tilde{\Omega}\left(2^{n/4}\right)$次经典随机查询，突显了一次精确量子查询的强大能力。 我们还研究了这个问题的一个受限变体，其中输入$f,g$可以由小的经典电路计算，并在密码学假设下展示了经典难度。
The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to $n$-bit Boolean functions $f$ and $g$, the goal is to estimate the Forrelation function $\mathrm{forr}(f,g)$, which measures the correlation between $g$ and the Fourier transform of $f$. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely $(f,g)$ with $\mathrm{forr}(f,g)=1$ and $\mathrm{forr}(f,g)=-1$. We show that this problem can be solved with one quantum query and success probability one, yet requires $\tilde{\Omega}\left(2^{n/4}\right)$ classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs $f,g$ are computable by small classical circuits and show classical hardness under cryptographic assumptions.
交叉提交 (展示 2 之 2 条目 )
- [4] arXiv:2403.00098 (替换) [中文pdf, pdf, 其他]
-
标题： 关于Skolem问题的计数复杂性标题： On the Counting Complexity of the Skolem Problem评论： 本文的结果已经是已知的主题： 计算复杂性 (cs.CC) ; 计算机科学中的逻辑 (cs.LO)
Skolem问题要求，给定一个整数线性递推序列（LRS），确定该序列是否包含零项。 其可判定性是理论计算机科学和自动机理论中的一个长期悬而未决的问题。 目前，仅知道阶数不超过4的LRS具有可判定性。 另一方面，唯一已知的复杂度结果是NP难性，由Blondel和Portier提出。 这一领域的一个基本成果是著名的Skolem-Mahler-Lech定理，该定理断言，任何LRS的零点集都是有限集合和有限多个等差数列的并集。 本文从计算的角度研究Skolem-Mahler-Lech定理：我们证明了给定LRS的零点计数问题是#P难的，并且实际上在我们的归约中生成的实例是#P完全的。
The Skolem Problem asks, given an integer linear recurrence sequence (LRS), to determine whether the sequence contains a zero term or not. Its decidability is a longstanding open problem in theoretical computer science and automata theory. Currently, decidability is only known for LRS of order at most 4. On the other hand, the sole known complexity result is NP-hardness, due to Blondel and Portier. A fundamental result in this area is the celebrated Skolem-Mahler-Lech theorem, which asserts that the zero set of any LRS is the union of a finite set and finitely many arithmetic progressions. This paper focuses on a computational perspective of the Skolem-Mahler-Lech theorem: we show that the problem of counting the zeros of a given LRS is #P-hard, and in fact #P-complete for the instances generated in our reduction.
- [5] arXiv:2501.12365 (替换) [中文pdf, pdf, html, 其他]
-
标题： 广义$q$-元函数的稀疏傅里叶变换的高效算法标题： Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions主题： 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 信息论 (cs.IT) ; 机器学习 (cs.LG)
计算一个$q$元函数的傅里叶变换，$f:\mathbb{Z}_{q}^n\rightarrow \mathbb{R}$，它将$q$元序列映射到实数，是数学中的一个重要问题，在生物学、信号处理和机器学习中有广泛的应用。 先前的研究表明，在稀疏性假设下，可以使用快速且样本高效的算法有效地计算傅里叶变换。 然而，在大多数实际情况下，该函数定义在一个更一般的空间——广义$q$元序列空间$\mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots \times \mathbb{Z}_{q_n}$——其中每个$\mathbb{Z}_{q_i}$对应于模$q_i$的整数。 在此，我们开发了GFast，一种编码理论算法，该算法计算$S$-稀疏傅里叶变换的$f$，其样本复杂度为$O(Sn)$，计算复杂度为$O(Sn \log N)$，并且失败概率随着$N=\prod_{i=1}^n q_i \rightarrow \infty$而趋近于零，其中$S = N^\delta$对于某些$0 \leq \delta < 1$而言。 我们证明了噪声鲁棒版本的GFast在相同的高概率保证下，以样本复杂度$O(Sn^2)$和计算复杂度$O(Sn^2 \log N)$计算变换。 此外，我们展示了GFast在合成实验中使用$16\times$更少的样本，更快地计算广义$q$-元函数$8\times$的稀疏傅里叶变换，并且与现有傅里叶算法相比，能够使用最多$13\times$更少的样本解释现实世界的心脏病诊断和蛋白质适应性模型，这些算法应用于模型最有效的参数化形式作为$q$-元函数。
Computing the Fourier transform of a $q$-ary function $f:\mathbb{Z}_{q}^n\rightarrow \mathbb{R}$, which maps $q$-ary sequences to real numbers, is an important problem in mathematics with wide-ranging applications in biology, signal processing, and machine learning. Previous studies have shown that, under the sparsity assumption, the Fourier transform can be computed efficiently using fast and sample-efficient algorithms. However, in most practical settings, the function is defined over a more general space -- the space of generalized $q$-ary sequences $\mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots \times \mathbb{Z}_{q_n}$ -- where each $\mathbb{Z}_{q_i}$ corresponds to integers modulo $q_i$. Herein, we develop GFast, a coding theoretic algorithm that computes the $S$-sparse Fourier transform of $f$ with a sample complexity of $O(Sn)$, computational complexity of $O(Sn \log N)$, and a failure probability that approaches zero as $N=\prod_{i=1}^n q_i \rightarrow \infty$ with $S = N^\delta$ for some $0 \leq \delta < 1$. We show that a noise-robust version of GFast computes the transform with a sample complexity of $O(Sn^2)$ and computational complexity of $O(Sn^2 \log N)$ under the same high probability guarantees. Additionally, we demonstrate that GFast computes the sparse Fourier transform of generalized $q$-ary functions $8\times$ faster using $16\times$ fewer samples on synthetic experiments, and enables explaining real-world heart disease diagnosis and protein fitness models using up to $13\times$ fewer samples compared to existing Fourier algorithms applied to the most efficient parameterization of the models as $q$-ary functions.
- [6] arXiv:2507.15511 (替换) [中文pdf, pdf, html, 其他]
-
标题： 证书敏感子集和：实现实例复杂性标题： Certificate-Sensitive Subset Sum: Realizing Instance Complexity评论： 15页+附录。arXiv:2503.20162的配套材料（“超越最坏情况的子集和问题：一种具有次2^{n/2}枚举的自适应、结构感知求解器”）主题： 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS)
我们据知，这是首个针对规范NP完全问题的确定性、证书敏感算法，其运行时间可证明地适应每个输入的结构。 对于一个子集和实例$(S, t)$，令$\Sigma(S)$表示不同的子集和的集合，并定义$U = |\Sigma(S)|$。 这个集合作为信息理论意义上的最小见证，即实例复杂度（IC）证书。 我们的求解器 IC-SubsetSum 以确定性时间$O(U \cdot n^2)$和空间$O(U \cdot n)$枚举$\Sigma(S)$的每一个元素。 一种随机变体实现了期望运行时间$O(U \cdot n)$。 该算法的复杂度因此直接由证书大小决定，这种结构敏感性能与一个保证的最坏情况运行时间$O^*(2^{n/2 - \varepsilon})$相匹配，对于某个常数$\varepsilon > 0$，这是首次在每个实例上严格优于经典方法的结果。 我们重新审视依赖于子集和问题的经典$2^{n/2}$硬度的细粒度归约，并表明这些论证仅在$U$最大化的无冲突实例中成立。 IC-SubsetSum从结构上重新提出了这一障碍，并为NP完全问题中的证书敏感算法引入了一个新范式。
We present, to our knowledge, the first deterministic, certificate-sensitive algorithm for a canonical NP-complete problem whose runtime provably adapts to the structure of each input. For a Subset-Sum instance $(S, t)$, let $\Sigma(S)$ denote the set of distinct subset sums and define $U = |\Sigma(S)|$. This set serves as an information-theoretically minimal witness, the instance-complexity (IC) certificate. Our solver, IC-SubsetSum, enumerates every element of $\Sigma(S)$ in deterministic time $O(U \cdot n^2)$ and space $O(U \cdot n)$. A randomized variant achieves expected runtime $O(U \cdot n)$. The algorithm's complexity is thus directly governed by the certificate size, and this structure-sensitive performance is paired with a guaranteed worst-case runtime of $O^*(2^{n/2 - \varepsilon})$ for some constant $\varepsilon > 0$, the first such result to strictly outperform classical methods on every instance. We revisit fine-grained reductions that rely on the classical $2^{n/2}$ hardness of SubsetSum and show that these arguments hold only for collision-free instances where $U$ is maximal. IC-SubsetSum reframes this barrier structurally and introduces a new paradigm for certificate-sensitive algorithms across NP-complete problems.
- [7] arXiv:2506.03014 (替换) [中文pdf, pdf, html, 其他]
-
标题： 有界阶系统量子虚时演化的收敛性和效率证明标题： Convergence and efficiency proof of quantum imaginary time evolution for bounded order systems评论： 16页主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC) ; 计算物理 (physics.comp-ph)
许多当前和未来近期的量子计算应用利用参数化的量子电路族和变分方法来找到这些参数的最佳值。 通过此类变分方法解决量子计算问题依赖于最小化某个代价函数，例如物理系统的能量。 因此，这类似于机器学习中的训练过程，因此变分量子模拟可能会遇到与机器学习训练中相似的问题。 这包括由于局部最小值而无法收敛到全局最小值以及临界减速。 在本文中，我们分析了虚时间演化作为一种编译参数化量子电路并找到最佳参数的方法，并表明它保证收敛到全局最小值而无需临界减速。 我们还表明，如果底层物理系统是有限阶的，那么编译过程，包括寻找最佳参数的任务，可以高效地进行到任意误差阈值。 这包括许多相关的计算问题，例如局部物理理论和组合优化问题，如航班到登机口分配问题。 特别是，我们对这些组合优化问题的成功概率给出了先验估计。 似乎没有已知的经典方法具有类似的效率和收敛保证。 同时，虚时间演化方法可以在当前的量子计算机上实现。
Many current and near-future applications of quantum computing utilise parametric families of quantum circuits and variational methods to find optimal values for these parameters. Solving a quantum computational problem with such variational methods relies on minimising some cost function, e.g., the energy of a physical system. As such, this is similar to the training process in machine learning and variational quantum simulations can therefore suffer from similar problems encountered in machine learning training. This includes non-convergence to the global minimum due to local minima as well as critical slowing down. In this article, we analyse the imaginary time evolution as a means of compiling parametric quantum circuits and finding optimal parameters, and show that it guarantees convergence to the global minimum without critical slowing down. We also show that the compilation process, including the task of finding optimal parameters, can be performed efficiently up to an arbitrary error threshold if the underlying physical system is of bounded order. This includes many relevant computational problems, e.g., local physical theories and combinatorial optimisation problems such as the flight-to-gate assignment problem. In particular, we show a priori estimates on the success probability for these combinatorial optimisation problems. There seem to be no known classical methods with similar efficiency and convergence guarantees. Meanwhile the imaginary time evolution method can be implemented on current quantum computers.
- [8] arXiv:2506.10876 (替换) [中文pdf, pdf, html, 其他]
-
标题： 兰道尔原理与计算热力学标题： Landauer Principle and Thermodynamics of Computation期刊参考： 代表。 进展。 物理。 88 086001，2025主题： 量子物理 (quant-ph) ; 统计力学 (cond-mat.stat-mech) ; 计算复杂性 (cs.CC) ; 形式语言与自动机理论 (cs.FL)
根据兰道尔原理，任何逻辑上不可逆的过程都会伴随熵的产生，这会导致环境中的热量耗散。 信息擦除是主要的逻辑上不可逆过程之一，它在向环境中散发的热量存在一个下限，称为兰道尔极限（LB）。 然而，实际的擦除过程会散发比LB多得多的热量。 最近，有一些实验研究在经典和量子领域都试图达到这个极限。 在量子领域中，也出现了一波研究热潮，探讨在有限时间、有限大小的热浴、非马尔可夫和非平衡环境中这一LB，此时系统与热浴的涨落和相关性效应不能再被忽略。 本文对兰道尔极限的最新进展进行了全面综述，它在计算热力学中是一个基本原理。 我们还提供了对未来这些方向研究的视角。 此外，我们回顾了最近在建立计算过程能量极限方面的探索。 我们还讨论了纠错的热力学方面，这是信息处理和计算中不可或缺的一部分。 在这一过程中，我们简要讨论了这些领域的基础知识，以提供一个完整的图景。
According to the Landauer principle, any logically irreversible process accompanies entropy production, which results in heat dissipation in the environment. Erasing of information, one of the primary logically irreversible processes, has a lower bound on heat dissipated into the environment, called the Landauer bound (LB). However, the practical erasure processes dissipate much more heat than the LB. Recently, there have been a few experimental investigations to reach this bound both in the classical and quantum domains. There has also been a spate of activities to enquire about this LB in finite time, with finite-size heat baths, non-Markovian and nonequilibrium environments in the quantum regime, where the effects of fluctuations and correlation of the systems with the bath can no longer be ignored. This article provides a comprehensive review of the recent progress on the Landauer bound, which serves as a fundamental principle in the thermodynamics of computation. We also provide a perspective for future endeavors in these directions. Furthermore, we review the recent explorations toward establishing energetic bounds of a computational process. We also discuss the thermodynamic aspects of error correction, which is an indispensable part of information processing and computations. In doing so, we briefly discuss the basics of these fields to provide a complete picture.