可积砖墙电路中算符纠缠的平方根增长反例
作者给出一个四态可积砖墙电路反例，其中局部算符的冯·诺伊曼纠缠以 加上 的形式增长，而固定指标的 Rényi 纠缠在指标低于1时线性增长、高于1时对数增长。
动态展示门槛：AI 前沿与应用 ≥ 70 分，量子方向 ≥ 62 分；已确认精选照常展示。
#复杂性
arXiv · quant-ph arXiv · quant-ph 研究者提出无需 conditioning 的非均匀量子 Fourier 与 Chebyshev 变换算法
作者提出一种无需 conditioning 的非均匀 Chebyshev 变换量子算法，适用于在 x∈[-1,1] 上均匀、在角度 θ=arccos x 上非均匀的 Chebyshev 节点，并使误差界不再依赖既有方法中的几何参数 κ。
arXiv · quant-ph Minbo Gao、Tianshi Yu 和 Lihong Zhi 通过线性系统博弈构造 Tsirelson 问题逼近形式的显式反例
Minbo Gao、Tianshi Yu 和 Lihong Zhi 构造了一个显式二元线性系统博弈，分离有限维量子相关集 C_qa 与对易算符相关集 C_qc。
arXiv · quant-ph 经典优化问题的量子近似复杂度研究
作者定义 BQ-APX、BQ-PTAS 和 BQ-FPTAS，用于刻画有界误差量子算法对经典优化问题可保证的近似质量，要求统一量子算法以至少 2/3 的概率返回可行解。
arXiv · quant-ph 归一化线性泛函的量子读出复杂度：目标依赖易感度决定解态拷贝数
基于论文摘要，作者研究了从编码了解向量 q 的量子态估计归一化线性泛函 F_φ(q) 的输出接口复杂度，并提出目标依赖易感度 χ_φ 来描述所需解态拷贝数。对于固定正参考态及其邻域，摘要给出最优未知态拷贝数为 ，其中 ε 是绝对误差容忍度、β 是允许失败概率；两个固定单拷贝测量可达到相同速率。
arXiv · quant-ph Christine Li 与 Natalie Parham 建立量子态制备下界的 natural proofs 屏障
Christine Li 与 Natalie Parham 在论文摘要中提出量子态制备下界的 natural proofs 屏障：若一个性质对足够大比例的 Haar 随机量子态成立，且在给定全部振幅时可高效测试，则在标准密码学假设下，不能用它证明超多项式态制备下界，即使针对固定层级的 Magic Hierarchy。
arXiv · quant-ph精选 稳定子扩展度与 Clifford 秩上界的改进
基于论文摘要，作者证明稳定子秩不超过k的纯态具有至多2^{}的稳定子扩展度，并为Clifford秩为k的算符建立类似的平方Clifford系数范数界。
本站判断：论文围绕稳定子秩、Clifford 秩及其与幅度范数的关系，改进了相关上界和下界，并将结果应用于稳定子保真度、张量幂、伪随机态集与 tomography 算法。基于摘要，这些贡献主要是理论结果，实际算法复杂度和应用影响仍取决于完整证明及所采用的复杂度模型。
arXiv · quant-ph CV-QAOA：连续变量量子优化的低深度方法
作者提出连续变量量子近似优化算法CV-QAOA，用于高维连续优化，并证明其在多类成本函数上的性能保证。
arXiv · quant-ph Yadavalli等提出面向不可信用户的1/2BQP_1受限量子计算模型
Shiv Akshar Yadavalli、Joel Rajakumar、Alexander Schuckert和Michael J. Gullans提出1/2BQP_1模型，量子服务器提供执行后才揭示的随机计算基输入，并仅返回一位输出。
arXiv · quant-ph 量子p自旋模型提出近似高效的Gibbs态经典采样算法
Saleh Naghdi与Eric R. Anschuetz提出一种对量子p自旋模型Gibbs态进行采样的经典算法，可将总变差距离误差降至多项式小水平。方法基于ASL元算法，其关键技术是将任意超立方体分布的采样约化为相关“倾斜分布”的均值估计，并扩展已知的拟多项式时间算法处理量子p自旋模型。
arXiv · quant-ph 研究确定集体对角酉变换的精确 LCU 采样开销及连分数分类
作者基于论文摘要证明，集体对角酉变换在一层单比特旋转上的最小 LCU 采样开销由 γ/π 的连分数决定。对最简有理角 πp/q，当 n≥2q−2 时，开销恰为 q，且均匀 q 点采样器达到该结果；开销随 n 呈 当且仅当 γ/π 坏可逼近，随 n 有界当且仅当其为有理数。
arXiv · quant-ph 纯化资源使顺序量子信道判别获得无界查询分离
作者证明，顺序访问纯化量子信道可使量子信道判别相对未纯化查询获得无界优势。摘要报告了两类量子比特信道结果：一类在两次查询下产生严格成功概率分离，另一类的纯化资源三次查询即可完美判别，而未纯化查询无论有限多少次都无法实现完美判别；研究还指出这一分离强化了顺序策略相对并行策略的优势。
arXiv · quant-ph 经典与量子Gibbs态制备的绝热跟踪与最优调度
作者提出经典与量子优化算法的离散绝热Gibbs态制备框架，基于有限时间非齐次可逆Markov链推导跟踪定理和步复杂度界，并构造由谱隙与能量涨落控制的调度。
arXiv · quant-ph 一维量子 Gibbs 采样器在任意固定正温度下实现快速混合
基于论文摘要，作者证明一般一维非交换局域自旋系统的量子 Gibbs 采样器在任意固定正温度下均可快速混合：对含 n 个站点的系统，KMS 详细平衡采样器从任意初始状态达到迹范数误差 ε 的时间为 ，优于此前 的界。
arXiv · quant-ph 高阶网络Hodge Laplacian线性方程求解的量子复杂性
论文证明，在指定的稀疏预言机模型和参数承诺下，制备编码Hodge Laplacian线性方程归一化最小范数解的量子态是BQP困难的。作者通过一系列可高效恢复前序线性方程归一化最小范数解的归约，并结合相关判定问题的量子算法，证明该问题为BQP完备；以上结论基于论文摘要。
arXiv · quant-ph 变分量子算法训练即使是局部极小值也具有强NP困难性
作者证明，变分量子算法的训练目标即使可高效经典求值，寻找局部极小值仍具有强NP困难性。研究还表明，对于所有p≥1，在与某个局部极小值的ℓ_p距离严格小于π/2内寻找参数向量也保持该困难性；作者通过显式构造量子电路将这些困难实例归约为VQA训练问题。
arXiv · quant-ph 费米子随机性的 Magic 成本
作者在论文摘要中提出，费米子随机性需要随系统规模增长的非高斯输入资源：对于4N模式上由有界大小块组成的纯半填充态，一体缺陷密度达到最大时 asymptotically 可恢复完整的Porter-Thomas矩层级。归一化碰撞矩的渐近值为2N/ν，ν为自然轨道占据方差之和；该量还下界确定性精确制备中非高斯资源模式与保宇称局域门的组合成本，并可由两拷贝数涨落直接测量。
arXiv · quant-ph 量子擦除信道上的量子态盲传输
Remi A. Chou研究无初始共享纠缠、使用独立信道和认证公开经典通信的量子态盲传输，给出有限码长逆向界与可达界，并在诚实但好奇情形下证明二者匹配。其恶意安全构造结合交互哈希和信道输出测试，将每个输入分散到多个量子比特上，即使输入与外部参考系纠缠，也能向恶意接收者隐藏完整输入；摘要进一步报告恶意与诚实但好奇情形具有相同容量。
arXiv · quant-ph精选 相关性决定浅电路量子优势的可验证测试
作者提出一种仅凭经典样本检验常深度量子电路是否相对浅层经典电路具有优势的方法，指出关键在于经典采样器的单比特和成对相关性，而非距离。基于论文摘要，该测试包含一个由Lean 4机器证明的塌缩定理，并报告第五种相关性检查能够识别四种自然检查无法发现的远离目标的构造；实验落地仍受43量子比特、近0.99保真度纠缠资源状态限制。
本站判断：该研究把常深度量子电路相对浅层经典电路的优势检验，转化为对经典采样器单比特与成对相关性的分析，并给出基于不等式的测试。作者报告了Lean 4机器证明的塌缩定理及若干检查的有效性和可靠性边界；结论目前针对有限输入门类，距离和随机性受限的实验还受43量子比特、近0.99保真度纠缠资源约束，推广到完整类别仍取决于两个开放问题。
arXiv · quant-ph 高效量子态同一性判定：互补深度与样本复杂度算法
作者针对未知纯量子态的同一性判定问题，在固定重叠参数ε∈(0,1/4)下提出两种互补量子算法。第一种利用并行交换测试实现常数电路深度，并使用O(log(n/δ)log(2/δ))份每个输入态的副本；第二种利用Schur transform将样本复杂度降至O(log(n/δ))。
arXiv · quant-ph QCPH/mpoly 与 QCPH 的塌缩等价条件
作者定义非统一计算量子多项式时间层级 QCPH/mpoly，并证明它塌缩当且仅当量子多项式时间层级 QCPH 塌缩。研究还表明，若 coQCMA 包含于 QCMA/mpoly，则 QCPH 也会塌缩；QCPH/mpoly 可视为带有非统一量子验证器电路的 QCPH 类似物。
arXiv · quant-ph 译码量子干涉测量在流式场景下获得指数级量子优势
基于论文摘要，作者证明译码量子干涉测量（DQI）在流式设置中具有可证明的量子优势。针对由 Hermite 插值和 Hasse 导数定义的多项式约束问题，量子算法单遍读取输入、满足93%的约束，并使用多对数空间及每个输入条目的多对数计算时间；满足76%约束的经典算法则需要多项式空间，即使允许多项数次读取和无限时间。
arXiv · quant-ph 基于分数块灵敏度的含噪量子查询复杂性下界
基于论文摘要，Mehil Agarwal、Shravas Rao 和 Fang Song 以分数块灵敏度（fbs）研究不完美预言机访问下的量子查询复杂度，证明疏忽型预言机、混合查询及独立去相位噪声的多种下界。
arXiv · quant-ph Tal Barak 完整证明加权有谱隙 Clique Homology 的 QMA₁ 困难性
Tal Barak 完整证明了固定高效可计算的 k(n) 和逆多项式 γ(n) 下，加权有谱隙 clique homology 对 QMA₁(\mathcal G) 困难。
arXiv · quant-ph 解码量子干涉在近似优化中建立可证明的量子优势
作者在成员查询预言机模型下证明，解码量子干涉（DQI）在折叠最优多项式交集任务中的近似比严格高于任何多项式时间经典算法。典型采样实例上，改进版DQI获得更高分数保证；码率为0.3时，DQI的期望分数约为0.85，而经典算法要以常数概率超过0.65需要超多项式数量的成员查询。
arXiv · quant-ph精选 几何局域哈密顿量模拟获得近最优电路深度
论文作者针对固定维度晶格上的几何局域、时间无关且有限程哈密顿量，构造最近邻量子电路以模拟其时间T的动力学，电路深度为O(T log(nT/ε))、门数为O(nT log(nT/ε))，将既有结果中的多个对数开销压缩为单个对数。
本站判断：论文摘要给出几何局域、时间无关且有限程的晶格哈密顿量动力学模拟电路深度上界，并通过高精度校正将对数因子从多个压缩至单个对数；针对均匀XXZ哈密顿量的无条件下界则表明该结果在指定范围内接近最优。当前证据仅来自摘要，实际模拟开销、误差口径和有限规模实现仍需结合全文核对。本站设想：可在相同演化时间、精度和晶格维度条件下，比较该构造与已有方法的总门数、采样及编码成本。
arXiv · quant-ph 纠缠图着色复杂性研究证明三色以上问题不可判定
研究作者将经典约束满足问题的多态归约推广为保留间隙的纠缠约束满足问题归约，并证明三色以上的纠缠图着色问题不可判定。该结果为纠缠非局域游戏的决策复杂性提供了新的归约方法，相关结论基于论文摘要。
arXiv · quant-ph 随机量子线路超越矩匹配的分布精度界
基于论文摘要，作者证明强 ε-近似酉 k-设计在 n 个量子比特上，使每个输出概率的分布与有限维 Porter-Thomas 分布的 Kolmogorov 距离不超过 O(sqrt(2^n/[k(k+2^n)])+ε)，并指出该界在常数因子意义下最优。
arXiv · quant-ph精选 具有最大列欧几里得范数最优依赖的稀疏哈密顿量模拟算法
Zecheng Li和Chunhao Wang提出一种模拟d稀疏厄米哈密顿量的量子算法；当tΛ≥1/2时，以O(tΛ√d+√d log(2/ε))次稀疏预言机查询实现算子范数误差ε，消除了Low算法中的次多项式开销。
本站判断：该研究针对稀疏厄米哈密顿量模拟中的查询复杂度与精度开销，给出对最大列欧几里得范数具有最优依赖的算法；在适用参数范围内达到最坏情形下界。依据仅为论文摘要，实际查询复杂度还取决于稀疏预言机实现、态制备方式及门数换算。本站设想：可在相同稀疏访问模型和精度要求下，比较该算法与Low算法及经典稀疏矩阵方法的总查询与门成本。
arXiv · quant-ph Clifford 电路综合的一个变体被证明为 NP 完全
基于论文摘要，作者证明最优 Clifford 电路综合的一个变体是 NP 困难的，并给出其 NP 完全性相关结果。研究将 3-正则图的 3-边着色归约为仅使用 CZ 门的电路综合问题，进一步分析加入 Hadamard、phase 和 CNOT 门对最优深度的影响；作者据此指出，Clifford 酉矩阵是否存在规定深度内的实现属于 NP 完全问题。
arXiv · quant-ph精选 双图性与扩张性测试获得近似最优的 \widetilde{\Omega}(N^{1/3}) 量子查询下界
Chandrima Kayal、Sayantan Sen 和 Dániel Szabó 在基于论文摘要的研究中证明了双图性与扩张性测试均需要 \widetilde{\Omega}(N^{1/3}) 次量子查询。该结果将两类问题在多项式对数因子意义下的量子查询复杂度刻画为近似最优，方法依赖中间问题、归约以及对多项式的更精细分析。
本站判断：基于论文摘要，该研究将双图性和扩张性测试的量子查询下界推进至近似紧的 \widetilde{\Omega}(N^{1/3})，从而在多项式对数因子意义下刻画了两类问题的量子查询复杂度。证明通过引入与原问题相互归约的中间问题，并更精细地分析相关多项式；其影响主要针对量子查询模型，不直接涉及具体硬件实现。
arXiv · quant-ph 时间反演对称性认证的纠缠查询复杂度下界研究
研究作者提出仅使用前向访问和可信量子操作的时间反演对称性认证测试，并证明可靠区分时间反演对称 circular ensembles 与 Haar 随机 n 比特酉动力学需要 次查询，其中 e 为探针和测量的对数纠缠负性中的较小值。使用最大纠缠探针和 SWAP 测量可将查询次数降至常数，任意固定且兼容的探针与测量也可获得对应的复杂度关系。
arXiv · quant-ph 作者提出接近 CSS GV 界且可在线性门数、对数深度编码的量子 CSS 码
基于论文摘要，作者构造了速率—距离权衡接近 CSS GV 界的量子 CSS 码，其编码电路仅需对数深度和线性数量的门。该方法受 Brehm 和 Resch 的工作启发，可视为经典重复累积码的量子对应物；编码器由单个常数深度外层量子电路，以及多层经典累积和逆累积层组成。
arXiv · quant-ph 通过准过程函数刻画n量子比特酉变换
基于论文摘要，作者提出用准过程函数将任意n量子比特酉变换规范表示为准过程函数酉变换（qPFU），并用该表示理解无纠缠量子非定域性以及因果顺序与局域性的权衡。研究给出控制条件的互斥性（MECC）和无歧义性两个充分但非必要条件，且证明二者不等价；此外，作者将MECC酉变换的电路深度联系到Hamming图上的团划分问题，并据此给出深度界和过程函数酉纯化构造。
arXiv · quant-ph 从3SUM到在线SetDisjointness的量子细粒度下界
作者提出从3SUM到在线SetDisjointness的次线性时间量子约简，并给出从3XOR出发的类似约简。基于论文摘要，这些结果将量子3SUM猜想转化为具有O(N^p)预处理时间和O(N^q)查询时间的量子SetDisjointness算法的p+2q≥1权衡下界。
arXiv · quant-ph 平坦连接图上 st-态运输的量子算法
基于论文摘要，Jeffery、Osborne 和 Pass 研究了边缘携带酉操作且满足平坦连接条件的图上的 st-态运输问题，并提出运行时间为 、空间复杂度为 的有界错误量子算法。
arXiv · quant-ph精选 研究证明非局域量子计算无法完美实现近乎所有双量子比特酉变换
基于论文摘要，作者证明对于双量子比特，Haar 意义下几乎所有酉变换都无法通过有限维纠缠资源和单轮同时量子通信实现精确的非局域量子计算，即使资源和局域操作可针对目标定制。固定架构只能覆盖有限个局部酉轨道，所有架构的并集也仅形成可数个轨道；此外，当相位为超越数时，受控相位变换不能实现精确协议，Haar 随机基中的秩一投影测量也几乎必然无法由有限维资源局域化。
本站判断：该研究揭示了非局域量子计算精确实现能力的结构性限制：固定架构只能覆盖有限个局部酉轨道，所有架构的并集也只有可数个轨道。作者还给出超越数相位目标与局域化测量不可实现的例子；其结论范围以有限维纠缠资源、单轮同时量子通信及摘要所述协议设定为界。
arXiv · quant-ph Juntai Zhou 与 Felix Leditzky 提出量子态判别样本复杂度混合时间方法
Juntai Zhou 和 Felix Leditzky 提出一种混合时间方法，用于估计量子态判别的样本复杂度，并证明几何均匀纯态集在量子同质混合时间与广义 Dobrushin 系数下具有紧估计。
arXiv · quant-ph 作者利用局域恢复通道实现多对数深度量子热态模拟
Hideaki Hakoshima、Atsushi Iwaki和Nobuyuki Yoshioka提出利用空间局域Petz恢复通道制备非对易局域哈密顿量量子热态的方法，在固定空间维度下实现多对数深度电路。