XiaoMi-AI文件搜索系统
World File Search SystemQAOA
3-SAT 的 Grover-QAOA：二次加速，一般
摘要 SAT 问题是计算复杂性理论中具有根本重要性的典型 NP 完全问题，在科学和工程领域有许多应用；因此，它长期以来一直是经典算法和量子算法的重要基准。这项研究通过数值证据证明了 Grover 量子近似优化算法 (G-QAOA) 比随机抽样在寻找 3-SAT (All-SAT) 和 Max-SAT 问题的所有解方面具有二次加速。与 Grover 算法相比，G-QAOA 占用的资源更少，更适合解决这些问题，并且在对所有解进行抽样的能力方面超越了传统的 QAOA。我们通过对数千个随机 3-SAT 实例进行多轮 G-QAOA 的经典模拟来展示这些优势。我们还观察到 IonQ Aria 量子计算机上 G-QAOA 在小型实例方面的优势，发现当前硬件足以确定和采样所有解决方案。有趣的是，在每一轮 G-QAOA 中使用相同角度对的单角度对约束大大降低了优化 G-QAOA 角度的传统计算开销，同时保持了其二次加速。我们还发现了角度的参数聚类。单角度对协议和参数聚类显著减少了对 G-QAOA 角度进行传统优化的障碍。
使用同时吸收栅极吸收的最佳量子映射
摘要 - 在实现量子误差校正（QEC）之后，Quantum计算机专注于嘈杂的中间尺度量子（NISQ）应用。与需要QEC的众所周知的量子算法（例如Shor's或Grover的算法）相比，NISQ应用具有不同的结构和属性，可以利用编译。编译的关键步骤是将程序中的Qubits映射到给定量子计算机上的物理Qubit，这已被证明是一个难题。在本文中，我们提出了OLSQ-GA，这是一种最佳的量子映射器，具有同时交换闸门吸收期间的关键特征，我们表明这是NISQ应用程序非常有效的优化技术。与其他最先进的方法相比，量子近似优化算法（QAOA）是一个重要的NISQ应用，OLSQ-GA可将深度降低高达50.0％，将深度降低100％，这转化为55.9％的法律改善。OLSQ-GA的溶液最优性是通过精确的SMT公式实现的。为了获得更好的可伸缩性，我们以初始映射或交替匹配的形式增强了方法，从而使OLSQ-GA加快了272倍的速度，而没有最佳损失。
HAMMER：利用错误结果的汉明行为提高噪声量子电路的保真度
具有数百个量子比特的量子计算机即将面世。不幸的是，高设备错误率对使用这些近期的量子系统为实际应用提供支持构成了重大挑战。在现有量子系统上执行程序会产生正确和错误的结果，但输出分布通常太嘈杂而无法区分它们。在本文中，我们表明错误结果不是任意的，而是在汉明空间中表示时表现出明确定义的结构。我们在 IBM 和 Google 量子计算机上的实验表明，最常见的错误结果在汉明空间中更有可能接近正确结果。我们利用这种行为来提高推断正确结果的能力。我们提出了汉明重构 (HAMMER)，这是一种后处理技术，它利用对汉明行为的观察来重建嘈杂的输出分布，从而使得到的分布具有更高的保真度。我们使用来自 Google 和 IBM 量子计算机的实验数据（这些计算机拥有 500 多个独特的量子电路）评估 HAMMER，并将解决方案质量平均提高了 1.37 倍。在 Google 公开的 QAOA 数据集上，我们表明 HAMMER 可以锐化成本函数景观上的梯度。
学习融合量子经典分布式优化技术的发电调度
摘要 量子计算的出现可能会彻底改变复杂问题的解决方式。本文提出了一种将量子计算、机器学习和分布式优化相结合的双循环量子经典解算法用于发电调度。目的是便于使用具有有限数量量子比特的嘈杂近期量子机来解决发电调度等实际电力系统优化问题。外循环是一种 3 块量子交替方向乘法器 (QADMM) 算法，该算法将发电调度问题分解为三个子问题，包括一个二次无约束二进制优化 (QUBO) 和两个非 QUBO。内循环是一种可训练量子近似优化算法 (T-QAOA)，用于在量子计算机上解决 QUBO。提出的 T-QAOA 将量子-经典机器的相互作用转化为序列信息，并使用循环神经网络通过适当的采样技术估计量子电路的变分参数。 T-QAOA 只需几次量子学习器迭代即可确定 QUBO 解决方案，而量子经典求解器则需要数百次迭代。外部 3 块 ADMM 协调 QUBO 和非 QUBO 解决方案以获得原始问题的解。讨论了所提出的 QADMM 保证收敛的条件。研究了两个数学和三个代际调度案例。在量子模拟器和经典计算机上进行的分析表明了所提算法的有效性。讨论了 T-QAOA 的优势，并与使用基于随机梯度下降的优化器的 QAOA 进行了数值比较。
构建用于张量网络量子电路模拟的最佳收缩树
摘要 - 基于张量网络的量子电路模拟中的关键问题之一是构造收缩树，它可以最大程度地减少模拟成本，其中可以在操作数量中表达成本作为模拟运行时间的代理。在各种应用领域中出现了同样的问题，例如组合科学计算，概率图形模型中的边缘化以及解决约束满意度问题。在本文中，我们将该问题的计算严重部分减少到一个线性排序之一，并演示如何利用该领域的现有方法在相同的运行时间内实现比现有最先进的方法更好的数量级。为此，我们引入了一种新型的多项式时间算法，用于从给定的顺序构造最佳收缩树。此外，我们引入了一个快速，高质量的线性订购求解器，并证明了其适用性，作为为收缩树提供订购的启发式。最后，我们将我们的求解器与量子电路模拟中构造收缩树构造收缩树的竞争方法比较了随机生成的量子近似优化算法最大切割电路，并表明我们的方法在大多数测试的量子电路上都取得了卓越的结果。可重复性：我们的源代码和数据可在https://github.com/cameton/hpec2022 ContractionTrees上获得。索引术语 - 收集树，张量网络，量子电路模拟，QAOA
用于 NMR 模型推断的量子近似贝叶斯计算
过去几年中，量子技术面临的核心挑战之一是寻找近期量子机器的有用应用 1 。尽管在增加量子比特数量和提高其质量 2、3 方面已经取得了长足的进步，但在不久的将来，我们预计可靠门的数量将受到噪声和退相干的限制——即所谓的嘈杂中尺度量子时代。因此，提出了混合量子-经典方法，以充分利用现有的量子硬件并用经典计算对其进行补充。最值得注意的是，量子近似优化算法（QAOA） 4 和变分量子特征求解器（VQE） 5 的发展。这两种算法都使用量子计算机来准备变分状态，其中一些变分状态可能无法通过经典计算获得，但使用经典计算机来更新变分参数。已经进行了大量实验，证明了这些算法的可行性 6 – 8 ，但它们对现实问题的影响仍不清楚。在基于模型的统计推断中，人们经常面临类似的问题。对于简单模型，可以找到似然值并使其最大化，但对于复杂模型，似然值通常是难以处理的 9,10。NMR 波谱就是一个很好的例子。对于应该使用的模型类型有很好的理解（公式 (1)），人们只需要确定适当的参数。然而，计算特定模型的 NMR 波谱需要在指数级大的希尔伯特空间中执行计算，这对经典计算机来说极具挑战性。这一特性是提出将 NMR 作为量子计算平台的最初动机之一。尽管已经证明 NMR 实验中不存在纠缠 12,13，但强相关性使其在经典上难以处理；也就是说，算子 Schmidt 秩呈指数增长，例如，这禁止有效的表示
![arxiv：2305.07323v1 [Quant-ph] 2023年5月12日](/simg/g:\will\search\icon\source\7\72e4d14110db7165c8f2af0f5661c84c4ea8ad29.webp)
arxiv：2305.07323v1 [Quant-ph] 2023年5月12日
量子计算在广泛的科学学科中越来越受欢迎，因为它可以解决长期存在的计算问题，而这些计算问题被认为与classical计算机相关。量子计算具有潜力的一个有前途的领域是在物流和财务等工业领域常见的NP -HARD优化问题的加速。有兴趣使用该技术来解决优化问题的量子计算领域的新移民没有关于量子计算机和算法的当前Capabilies的易于访问的信息来源。本文旨在对量子优化技术及其实际应用的全面概述，重点关注其近期噪音中级量表量子设备的潜力。本文首先要在经典和量子优化问题之间绘制相似之处，从而突出其概念上的相似性和差异。然后讨论量子硬件的两个主要范例：量子退火和基于门的量子计算。虽然量子退火器对于某些探密问题有效，但它们存在局限性，不能用于通用量子计算。相比之下，基于门的量子计算机具有通用量子计算的潜力，但它们面临着硬件限制和准确的门实现的挑战。本文提供了详细的数学讨论，其中引用了该领域的关键作品，以及与相关示例的更实际讨论。详细讨论了基于门的量子计算机，量子近似优化（QAO）算法和量子交替运算符ANSATZ（QAOA）框架上最流行的量子优化技术。但是，即使在硬件和降噪方面取得了进步，这些技术仍然尚不清楚这些技术是否会产生量子优势。本文以讨论量子优化技术面临的挑战以及进一步的研究和开发的需求，以确定实现量子优势的新方法。
![arXiv:2103.15689v2 [quant-ph] 2023 年 5 月 11 日](/simg/g:\will\search\icon\source\e\ecb00ac2d78e84bd5f9d1fea8ee65e0a2c3256db.webp)
arXiv:2103.15689v2 [quant-ph] 2023 年 5 月 11 日
量子资源的使用可以让我们改进计算[1]、通信[2]和模拟[3, 4]中的各种经典任务。费曼在他的开创性著作中认识到，模拟或计算量子系统的复杂性随着组成系统的粒子数量的增加而呈指数增长[3]。当提出的解决方案是采用另一个可控量子系统来模拟未知系统的动力学时，我们称之为模拟量子模拟。后者已成功用于典型案例，例如量子拉比模型[5–7]、动态卡西米尔效应[8–10]、杰恩斯-卡明斯和拉比晶格[11–13]、费米子系统[14–18]以及最近的玻色子采样[19]，仅举几例。此外，还可以实现数字量子模拟 [20]，并产生许多有趣的应用 [21]。沿着这些思路，量子计算应运而生，量子图灵机的正式提出 [22, 23]，具有量子加速的量子算法的发现 [24– 26]，量子门的通用集 [27] 和量子纠错 [28–30]。鉴于这整个方法基于单量子比特门 (SQG) 和双量子比特门的算法序列 [31]，因此可以称其为数字量子计算。在不同量子平台中这一范式的关键实现包括超导量子比特 [21, 32–34] 和离子阱 [35, 36] 中的实验。最近，参考文献 [1] 提出了一种创新的量子计算范式。 [37]，其中引入了数字模拟量子计算 (DAQC)。DAQC 将提供多功能性的数字方法与增强抗误差能力的模拟方法相结合，在相同的 NISQ 设备中表现出比纯数字方法更好的可扩展性。该方法被用于提出量子傅里叶变换 [38] 和量子近似优化算法 (QAOA) [39] 的实际实现。
黑盒特征选择的多项式量子加速
特征选择需要从给定数据集中创建特征子集，以在原始数据集和选定特征集之间建立高度互信息 (MI) 共享 [ 1 , 2 ]。形式上，给定一组特征 F = { f 1 , f 2 , · · · , fm }，其中 fi ∈ R d ，设 fi K 为 fi 在 K 中的维度所跨越的子空间上的投影，设 FK = { fi K } 为一组独立的 fi 。特征选择问题定义为从 F 中选择 K ⊂{ 1 , · · · , p }，使得 K 保留最多信息。虽然特征选择是经典计算中一个研究得很深入的课题 [ 3 – 6 ]，但在量子算法开发的背景下，特征选择仍然是一个相对较新的领域。这项任务被认为是 NP 难题 [ 7 ]，在没有关于数据集结构的先验信息的情况下，量子算法的加速上限是二次的。此前，针对特征选择问题，人们提出了容错和效用规模量子算法 [8]，但成功率参差不齐 [9-15]。其中，容错量子特征选择算法分别表现出多对数时间复杂度和二次加速比。多对数时间复杂度是由于问题中隐藏着某种代数结构，而二次加速比是当手头的 NP 完全问题的结构未知时量子算法的一般 Grover 加速比 [16]。其他量子方法是实现变分方法的效用规模量子算法。尽管分析此类算法很困难，但可以合理地假设，除非进一步利用问题结构，否则此类算法的量子加速比的上限就是 Grover 加速比。表示特征选择问题的一种常用方法是二次无约束优化问题 (QUBO)，可以使用经典和量子计算框架进行处理。在量子计算机上，我们既可以使用 Grover 型容错算法，也可以使用 VQE [ 17 ] 或 QAOA 型 [ 18 ] 效用规模算法来求解该问题。另一方面，当量子算法能够利用已知结构时，加速比可以更显著，比如当简化为尖峰张量分解时，加速比可以达到四次方 [ 19 ]，而当与计算 Betti 数相关时，加速比甚至可以达到指数级 [ 20 , 21 ]。这促使人们探究是否存在一类具有最小结构的问题，即用户对特征拥有稍多的信息，而量子算法可能会带来一些加速。这项工作旨在解决黑盒特征选择问题 (B2FS) 的这个问题，在某些假设下，将其表述为碰撞问题 [ 22 ]。利用 Brassard-Høyer-Tapp 算法（BHT 算法）[ 23 ]，一种已知的碰撞问题解决方案，我们提供了对已经高效的经典概率算法进行多项式加速的证明。据我们所知，这是已知的第一个针对最小结构化特征选择问题的量子加速。
![arXiv:2401.10985v1 [quant-ph] 2024 年 1 月 19 日 - Strathprints](/simg/g:\will\search\icon\source\d\d2a6589df0a17b2e0b7a74f2413f6dd5d76b9c90.webp)
arXiv:2401.10985v1 [quant-ph] 2024 年 1 月 19 日 - Strathprints
绝热近似 [ 1 , 2 ] 指出，对于足够慢变化的哈密顿量，初始本征态将保持在时间相关问题的相应本征态。这种近似构成了当前量子技术中许多方法的基础，包括绝热量子计算 [ 3 – 5 ]、退火 [ 6 , 7 ]、模拟 [ 8 – 10 ] 和量子门的应用 [ 11 ]。绝热近似的有效性取决于哈密顿量随时间的变化是否缓慢 [ 2 , 5 , 12 ]。相关时间尺度由其谱中间隙的倒数决定。在量子多体系统中，过渡区域的间隙与自由度数成反比，从而迫使任意缓慢的时间依赖性保持绝热状态。这导致了大量技术的开发，以控制量子系统并在没有绝热近似的情况下实现预期的结果，从而导致了绝热捷径的发展[ 13 ， 14 ]，量子最优控制[ 15 – 18 ]，以及绝热量子退火[ 19 ]。注意，绝热近似也可以在不需要任何谱隙存在的情况下定义[ 20 ， 21 ]。对于量子多体系统，由于求解与时间无关的薛定谔方程的复杂性，了解绝热近似在什么时间尺度上失效并不是一项简单的任务。如果哈密顿量变化太快，可能出现跨越谱隙的绝热激发，从而违反绝热性的定义（遵循相应的本征态）。反非绝热驱动方法 [ 22 – 24 ] 引入了额外的驱动项来抵消这些非绝热激发，从而将绝热条件强制为任意快时间内时间相关的薛定谔方程的解。然而，要做到这一点，恰恰需要了解特征态，而这又需要时间无关的薛定谔方程的解。由于这在许多情况下超出了当前计算机的能力范围，特别是对于基态以外的情况，因此需要开发一种新的绝热和反非绝热驱动方法。最近，提出了一种方法，它通过绝热规范势 (AGP) 定义非绝热激发，可以使用最小作用原理通过变分找到 [ 25 ， 26 ] 。即使不使用这种变分方法也可以找到精确的 AGP，但这又回到了有效求解薛定谔方程。变分方法允许构建近似反非绝热驱动，该驱动可以考虑实际实施的要求，例如控制项是局部的。因此，AGP 的概念已被用于构建各种量子多体模型的近似反非绝热驱动协议，包括为数值最优控制[27-30]提供信息，为机器学习方法提供灵感[31]，改进量子退火协议[32-35]，改进状态准备[36，37]，以及实现实验演示[38，39]。AGP 提供了大量有关量子系统动力学的信息 [26]，其探测感兴趣物理性质的能力仍在研究中。最近有研究表明，AGP 范数可以为简单模型提供量子相变的精确度量 [40]，也有研究将其用作量子混沌的度量 [41-43]。 AGP 可用于寻找量子近似优化算法 (QAOA) 的最优角度，其方式是将对非绝热损失的抑制纳入有限数量的变分步骤引起的 Trotter 误差中 [44-46]。研究还表明，AGP 可用于计算变分 Schrieffer-Wolff 变换，以计算多体动力学 [47]。在本文中，我们提出了一种新的、有效的数值方法来计算 AGP，它结合了参考文献 [25] 和 [48] 中的思想，以及参考文献 [40] 中的代数方法。我们的新方法可以生成任意阶的 AGP 近似值，同时允许