计算复杂性

• 交叉列表
• 替换

查看 最近的 文章

显示 2025年08月06日， 星期三 新的列表

交叉提交 (展示 1 之 1 条目 )

[1] arXiv:2508.03203 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]

标题： 量子电路中逻辑深度的热力学特征 显示英文标题

标题： Thermodynamic Signature of Logical Depth in Quantum Circuits

Issam Ibnouhsein

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC)

我们证明，在逐步退相干下，量子电路的内部逻辑结构可以留下明显的热力学特征。 通过将深度、条件分支电路与浅层、均匀电路进行比较——同时控制整体停止概率和物理资源——我们表明，分支架构会引发更多的熵流进入环境。 这种效应由一个逻辑深度因子$L_d$来描述，该因子量化了环境相互作用期间的熵积累。 我们通过详细分析两个4分支量子电路验证了我们的框架，展示了在条件架构与均匀架构之间，$L_d \approx 1.615$的熵产生更大。 一种基于辅助比特的实验协议，使用受控相位门，为在当前量子平台上检测这些热力学特征提供了一条具体的路径。 我们的结果确立了逻辑深度作为一个具有电路设计、编译策略和验证协议意义的物理可测量量。 显示英文摘要

We demonstrate that the internal logical structure of a quantum circuit can leave a distinct thermodynamic signature under progressive decoherence. By comparing deep, conditionally branching circuits with shallow, uniform counterparts-while controlling for overall halting probability and physical resources-we show that branching architectures induce greater entropy flow into the environment. This effect is captured by a logical depth factor $L_d$, which quantifies entropy accumulation during environmental interactions. We validate our framework through detailed analysis of two 4-branch quantum circuits, demonstrating greater entropy production with $L_d \approx 1.615$ for conditional versus uniform architectures. An ancilla-based experimental protocol using controlled-phase gates provides a concrete pathway for detecting these thermodynamic signatures on current quantum platforms. Our results establish logical depth as a physically measurable quantity with implications for circuit design, compilation strategies, and verification protocols.

替换提交 (展示 2 之 2 条目 )

[2] arXiv:1905.05669 (替换) [中文pdf, pdf, html, 其他]

标题： 计算的随机热力学 显示英文标题

标题： Stochastic thermodynamics of computation

David H. Wolpert

评论： 113页，无图表。arXiv管理员注释：与arXiv:1901.00386文本重叠

期刊参考： 为特刊“香农的信息理论：70年后”撰写的邀请文章，《物理学期刊A：数学与理论》，2019年

主题： 统计力学 (cond-mat.stat-mech) ; 计算复杂性 (cs.CC)

计算机的主要资源需求之一——从生物细胞到人脑再到高性能（工程化）计算机——是运行它们所使用的能量。 执行计算的成本长期以来一直是物理学研究的重点，可以追溯到Landauer的早期工作。 计算机最显著的特征之一是它们本质上是非平衡系统。 然而，早期的研究是在非平衡统计物理尚处于初期阶段时进行的，这意味着这些工作是用平衡统计物理的术语来表述的。 自那时以来，非平衡统计物理取得了重大突破，使我们能够研究统计物理与计算之间关系的诸多方面，远远超出了消除一个比特所需做功的问题。 在本文中，我回顾了一些关于“计算的随机热力学”的近期工作。 在回顾了信息论、计算机科学理论和随机热力学的关键部分之后，我总结了关于执行广泛计算的熵成本所学到的内容，这些计算从比特擦除扩展到无环电路、逻辑可逆电路、信息棘轮到图灵机。 这些结果揭示了如何设计具有最小热力学成本的计算机的新挑战性工程问题。 它们还使我们能够开始在基础层面上将计算机科学理论和随机热力学结合起来，从而拓展两者。 显示英文摘要

One of the major resource requirements of computers - ranging from biological cells to human brains to high-performance (engineered) computers - is the energy used to run them. Those costs of performing a computation have long been a focus of research in physics, going back to the early work of Landauer. One of the most prominent aspects of computers is that they are inherently nonequilibrium systems. However, the early research was done when nonequilibrium statistical physics was in its infancy, which meant the work was formulated in terms of equilibrium statistical physics. Since then there have been major breakthroughs in nonequilibrium statistical physics, which are allowing us to investigate the myriad aspects of the relationship between statistical physics and computation, extending well beyond the issue of how much work is required to erase a bit. In this paper I review some of this recent work on the `stochastic thermodynamics of computation'. After reviewing the salient parts of information theory, computer science theory, and stochastic thermodynamics, I summarize what has been learned about the entropic costs of performing a broad range of computations, extending from bit erasure to loop-free circuits to logically reversible circuits to information ratchets to Turing machines. These results reveal new, challenging engineering problems for how to design computers to have minimal thermodynamic costs. They also allow us to start to combine computer science theory and stochastic thermodynamics at a foundational level, thereby expanding both.

[3] arXiv:2411.02148 (替换) [中文pdf, pdf, html, 其他]

标题： 频率矩估计的最优性 显示英文标题

标题： Optimality of Frequency Moment Estimation

Mark Braverman, Or Zamir

评论： 此版本撤回了之前包含的一个草图，该草图声称下界应扩展到非整数频率矩F_p，其中p在(1,2)之间

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC) ; 信息论 (cs.IT)

估计流的第二个频率矩，最多需要$O(\log n / \varepsilon^2)$位空间，才能达到$(1\pm\varepsilon)$的乘法误差，这是 Alon、Matias 和 Szegedy 的开创性结果。 也已知至少需要$\Omega(\log n + 1/\varepsilon^{2})$的空间。 我们证明了对于所有$\varepsilon = \Omega(1/\sqrt{n})$，最优下界为$\Omega\left(\log \left(n \varepsilon^2 \right) / \varepsilon^2\right)$。 请注意，当$\varepsilon>n^{-1/2 + c}$，其中$c>0$，我们的下界与 AMS 的经典上界一致。 对于较小的$\varepsilon$值，我们还引入了一个改进的算法，该算法改进了经典的 AMS 界并匹配我们的下界。 显示英文摘要

Estimating the second frequency moment of a stream up to $(1\pm\varepsilon)$ multiplicative error requires at most $O(\log n / \varepsilon^2)$ bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least $\Omega(\log n + 1/\varepsilon^{2})$ space is needed. We prove an optimal lower bound of $\Omega\left(\log \left(n \varepsilon^2 \right) / \varepsilon^2\right)$ for all $\varepsilon = \Omega(1/\sqrt{n})$. Note that when $\varepsilon>n^{-1/2 + c}$, where $c>0$, our lower bound matches the classic upper bound of AMS. For smaller values of $\varepsilon$ we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound.