已经表明，可以使用具有合适的数据访问的经典算法有效地复制一些量子机器学习算法的表观优点 - 一种称为渐变化的过程。现有的追逐工作的工作比较量子算法占据N-qubit Quantum State $ | x \ rangle = \ sum_ {i} x_i | i \ rangle $的副本到具有样本和查询（Sq）访问的经典算法矢量$ x $。在本说明中，我们证明了具有SQ访问的经典算法可以比量子状态输入的量子算法呈指数级速率地实现一些学习任务。因为经典算法是量子算法的子集，所以这表明SQ接入有时可以比量子状态输入更强大。我们的研究结果表明，在某些学习任务中没有指数量子优势可能是由于相对于量子状态输入的SQ访问过于强大。如果我们将量子算法与量子状态的输入进行比较到具有对量子状态上的测量数据的经典算法，则量子优势的景观可以显着不同。

量子技术有可能彻底改变我们如何获取和处理实验数据以了解物理世界。一种实验设置，将来自物理系统的数据转换为稳定的量子存储器，以及使用量子计算机的数据的处理可以具有显着的优点，这些实验可以具有测量物理系统的传统实验，并且使用经典计算机处理结果。我们证明，在各种任务中，量子机器可以从指数较少的实验中学习而不是传统实验所需的实验。指数优势在预测物理系统的预测属性中，对噪声状态进行量子主成分分析，以及学习物理动态的近似模型。在一些任务中，实现指数优势所需的量子处理可能是适度的;例如，可以通过仅处理系统的两个副本来同时了解许多非信息可观察。我们表明，可以使用当今相对嘈杂的量子处理器实现大量超导QUBITS和1300个量子门的实验。我们的结果突出了量子技术如何能够实现强大的新策略来了解自然。

即使在数十年的量子计算开发之后，通常在经典同行中具有指数加速的通常有用量子算法的示例是稀缺的。线性代数定位量子机学习（QML）的量子算法中的最新进展作为这种有用的指数改进的潜在来源。然而，在一个意想不到的发展中，最近一系列的“追逐化”结果同样迅速消除了几个QML算法的指数加速度的承诺。这提出了关键问题是否是其他线性代数QML算法的指数加速度持续存在。在本文中，我们通过该镜头研究了Lloyd，Garnerone和Zanardi的拓扑数据分析算法后面的量子算法方法。我们提供了证据表明，该算法解决的问题通过表明其自然概括与模拟一个清洁量子位模型很难地难以进行棘手的 - 这被广泛认为需要在经典计算机上需要超时时间 - 并且非常可能免疫追逐。基于此结果，我们为等级估计和复杂网络分析等问题提供了许多新的量子算法，以及其经典侵害性的复杂性 - 理论上。此外，我们分析了近期实现的所提出的量子算法的适用性。我们的结果为全面吹嘘和限制的量子计算机提供了许多有用的应用程序，具有古典方法的保证指数加速，恢复了线性代数QML的一些潜力，以成为量子计算的杀手应用之一。

Learning about physical systems from quantum-enhanced experiments, relying on a quantum memory and quantum processing, can outperform learning from experiments in which only classical memory and processing are available. Whereas quantum advantages have been established for a variety of state learning tasks, quantum process learning allows for comparable advantages only with a careful problem formulation and is less understood. We establish an exponential quantum advantage for learning an unknown $n$-qubit quantum process $\mathcal{N}$. We show that a quantum memory allows to efficiently solve the following tasks: (a) learning the Pauli transfer matrix of an arbitrary $\mathcal{N}$, (b) predicting expectation values of bounded Pauli-sparse observables measured on the output of an arbitrary $\mathcal{N}$ upon input of a Pauli-sparse state, and (c) predicting expectation values of arbitrary bounded observables measured on the output of an unknown $\mathcal{N}$ with sparse Pauli transfer matrix upon input of an arbitrary state. With quantum memory, these tasks can be solved using linearly-in-$n$ many copies of the Choi state of $\mathcal{N}$, and even time-efficiently in the case of (b). In contrast, any learner without quantum memory requires exponentially-in-$n$ many queries, even when querying $\mathcal{N}$ on subsystems of adaptively chosen states and performing adaptively chosen measurements. In proving this separation, we extend existing shadow tomography upper and lower bounds from states to channels via the Choi-Jamiolkowski isomorphism. Moreover, we combine Pauli transfer matrix learning with polynomial interpolation techniques to develop a procedure for learning arbitrary Hamiltonians, which may have non-local all-to-all interactions, from short-time dynamics. Our results highlight the power of quantum-enhanced experiments for learning highly complex quantum dynamics.

我们提出了一个算法框架，用于近距离矩阵上的量子启发的经典算法，概括了Tang的突破性量子启发算法开始的一系列结果，用于推荐系统[STOC'19]。由量子线性代数算法和gily \'en，su，low和wiebe [stoc'19]的量子奇异值转换（SVT）框架[SVT）的动机[STOC'19]，我们开发了SVT的经典算法合适的量子启发的采样假设。我们的结果提供了令人信服的证据，表明在相应的QRAM数据结构输入模型中，量子SVT不会产生指数量子加速。由于量子SVT框架基本上概括了量子线性代数的所有已知技术，因此我们的结果与先前工作的采样引理相结合，足以概括所有有关取消量子机器学习算法的最新结果。特别是，我们的经典SVT框架恢复并经常改善推荐系统，主成分分析，监督聚类，支持向量机器，低秩回归和半决赛程序解决方案的取消结果。我们还为汉密尔顿低级模拟和判别分析提供了其他取消化结果。我们的改进来自识别量子启发的输入模型的关键功能，该模型是所有先前量子启发的结果的核心：$ \ ell^2 $ -Norm采样可以及时近似于其尺寸近似矩阵产品。我们将所有主要结果减少到这一事实，使我们的简洁，独立和直观。

我们建立了量子算法设计与电路下限之间的第一一般连接。具体来说，让$ \ mathfrak {c} $是一类多项式大小概念，假设$ \ mathfrak {c} $可以在统一分布下的成员查询，错误$ 1/2 - \ gamma $通过时间$ t $量子算法。我们证明如果$ \ gamma ^ 2 \ cdot t \ ll 2 ^ n / n $，则$ \ mathsf {bqe} \ nsubseteq \ mathfrak {c} $，其中$ \ mathsf {bqe} = \ mathsf {bque} [2 ^ {o（n）}] $是$ \ mathsf {bqp} $的指数时间模拟。在$ \ gamma $和$ t $中，此结果是最佳的，因为它不难学习（经典）时间$ t = 2 ^ n $（没有错误） ，或在Quantum Time $ t = \ mathsf {poly}（n）$以傅立叶采样为单位为1/2美元（2 ^ { - n / 2}）$。换句话说，即使对这些通用学习算法的边际改善也会导致复杂性理论的主要后果。我们的证明在学习理论，伪随机性和计算复杂性的几个作品上构建，并且至关重要地，在非凡的经典学习算法与由Oliveira和Santhanam建立的电路下限之间的联系（CCC 2017）。扩展他们对量子学习算法的方法，结果产生了重大挑战。为此，我们展示了伪随机发电机如何以通用方式意味着学习到较低的连接，构建针对均匀量子计算的第一个条件伪随机发生器，并扩展了Impagliazzo，JaiSwal的本地列表解码算法。 ，Kabanets和Wigderson（Sicomp 2010）通过微妙的分析到量子电路。我们认为，这些贡献是独立的兴趣，可能会发现其他申请。

我们研究量子存储器的力量，以了解量子系统和动态的学习性质，这在物理和化学方面具有重要意义。许多最先进的学习算法需要访问额外的外部量子存储器。虽然这种量子存储器不需要先验，但在许多情况下，不利用量子存储器的算法需要比那些更多样的数据。我们表明，这种权衡在各种学习问题中是固有的。我们的结果包括以下内容：（1）我们显示以$ M $ -Qubit状态Rho执行暗影断层扫描，以M $观察到，任何没有量子存储器的算法需要$ \ omega（\ min（m，2 ^ n） ）最坏情况下Rho的标准。达到对数因子，这与[HKP20]的上限匹配，完全解决了[AAR18，AR19]中的打开问题。 （2）我们在具有和不具有量子存储器之间的算法之间建立指数分离，用于纯度测试，区分扰扰和去极化的演变，以及在物理动态中揭示对称性。我们的分离通过允许更广泛的无量子存储器的算法来改善和概括[ACQ21]的工作。 （3）我们提供量子存储器和样本复杂性之间的第一个权衡。我们证明，估计所有$ N $ -Qubit Pauli可观察到的绝对值，Qumum Memory的$ K <N $ Qubits的算法需要至少$ \ omega（2 ^ {（nk）/ 3}）$样本，但在那里是使用$ n $ -Qubit量子存储器的算法，该算法只需要$ o（n）$ samples。我们展示的分离足够大，并且可能已经是显而易见的，例如，数十Qubits。这提供了一种具体的路径，朝着使用量子存储器学习算法的实际优势。

尽管经过多年的努力，但在经典数据的情况下，量子机学习社区只能显示出某些人为加密启发的数据集的量子学习优势。在本说明中，我们讨论了发现学习问题的挑战，即量子学习算法可以比任何经典学习算法更快学习，并研究如何识别此类学习问题。具体而言，我们反思了与此问题有关的计算学习理论中的主要概念，并讨论定义的细微变化在概念上意味着显着不同的任务，这可能会导致分离或根本没有分离。此外，我们研究了现有的学习问题，并具有可证明的量子加速，以提炼一组更一般和充分的条件（即``清单''），以表现出在经典学习者和量子学习者之间的分离的学习问题。这些清单旨在简化一个人的方法来证明学习问题或阐明瓶颈的量子加速。最后，为了说明其应用，我们分析了潜在分离的示例（即，当学习问题是从计算分离中或数据来自量子实验时）通过我们的方法的镜头进行分析。

量子计算有可能彻底改变和改变我们的生活和理解世界的方式。该审查旨在提供对量子计算的可访问介绍，重点是统计和数据分析中的应用。我们从介绍了了解量子计算所需的基本概念以及量子和经典计算之间的差异。我们描述了用作量子算法的构建块的核心量子子程序。然后，我们审查了一系列预期的量子算法，以便在统计和机器学习中提供计算优势。我们突出了将量子计算应用于统计问题的挑战和机遇，并讨论潜在的未来研究方向。

从样本中学习概率分布的任务在整个自然科学中无处不在。局部量子电路的输出分布构成了一类特别有趣的分布类别，对量子优势提案和各种量子机学习算法都具有关键的重要性。在这项工作中，我们提供了局部量子电路输出分布的可学习性的广泛表征。我们的第一个结果可以深入了解这些分布的有效学习性与有效的可模拟性之间的关系。具体而言，我们证明与Clifford电路相关的密度建模问题可以有效地解决，而对于深度$ d = n^{\ omega（1）} $电路，将单个$ t $ gate注入到电路中，这使这是如此问题很难。该结果表明，有效的模拟性并不意味着有效的可学习性。我们的第二组结果提供了对量子生成建模算法的潜在和局限性的见解。我们首先证明与深度$ d = n^{\ omega（1）} $局部量子电路相关的生成建模问题对于任何学习算法，经典或量子都很难。结果，一个人不能使用量子算法来为此任务获得实际优势。然后，我们证明，对于各种最实际相关的学习算法（包括混合量词古典算法），即使是与深度$ d = \ omega（\ log（n））$ Clifford Circuits相关的生成建模问题也是如此难的。该结果对近期混合量子古典生成建模算法的适用性造成了限制。

量子机学习（QML）模型旨在从量子状态中编码的数据中学习。最近，已经表明，几乎没有归纳偏差的模型（即，对模型中嵌入的问题没有假设）可能存在训练性和概括性问题，尤其是对于大问题。因此，开发编码与当前问题有关的信息的方案是至关重要的。在这项工作中，我们提出了一个简单但功能强大的框架，其中数据中的基本不向导用于构建QML模型，该模型通过构造尊重这些对称性。这些所谓的组不变模型产生的输出在对称组$ \ mathfrak {g} $的任何元素的动作下保持不变。我们提出了理论结果，基于$ \ mathfrak {g} $ - 不变型模型的设计，并通过几个范式QML分类任务来体现其应用程序，包括$ \ mathfrak {g} $是一个连续的谎言组，也是一个lie group，也是一个。离散对称组。值得注意的是，我们的框架使我们能够以一种优雅的方式恢复文献的几种知名算法，并发现了新的算法。综上所述，我们期望我们的结果将有助于为QML模型设计采用更多几何和群体理论方法铺平道路。

我们提出了第一近最优量子算法，用于估计欧几里德的规范，与有限均值和协方差的矢量值随机变量的平均值。我们的结果旨在将多元子高斯估计的理论延伸到量子设置。与经典上不同，如果任何单变量估计器都可以在维度中最多的对数开销转换为多变量估计器，则不会在量子设置中证明类似的结果。实际上，当样品复杂性小于尺寸时，Heinrich排除了平均估计问题的量子优势。我们的主要结果是表明，在这种低精度的方案之外，有一个量子估计值优于任何经典估算器。我们的方法比单变量设置大致涉及，大多数量子估计人员依赖于相位估计。我们利用各种额外的算法技术，如幅度放大，伯恩斯坦 - Vazirani算法和量子奇异值转换。我们的分析还使用多元截断统计的浓度不等式。我们以前在文献中出现的两个不同输入模型中的Quantum估算器。第一个提供对随机变量的二进制表示的相干访问，并且它包含经典设置。在第二模型中，随机变量直接编码到量子寄存器的相位中。该模型在许多量子算法中自然出现，但常常具有古典样品通常是无与伦比的。我们将我们的技术调整为这两个设置，我们表明第二种模型严格较弱，以解决平均估计问题。最后，我们描述了我们的算法的几个应用，特别是在测量通勤可观察到的期望值和机器学习领域时。

量子计算为某些问题提供了指数加速的潜力。但是，许多具有可证明加速的现有算法都需要当前不可用的耐故障量子计算机。我们提出了NISQ-TDA，这是第一个完全实现的量子机学习算法，其在任意经典（非手动）数据上具有可证明的指数加速，并且仅需要线性电路深度。我们报告了我们的NISQ-TDA算法的成功执行，该算法应用于在量子计算设备以及嘈杂的量子模拟器上运行的小数据集。我们从经验上证实，该算法对噪声是可靠的，并提供了目标深度和噪声水平，以实现现实世界中问题的近期，无耐受耐受性的量子优势。我们独特的数据加载投影方法是噪声鲁棒性的主要来源，引入了一种新的自我校正数据加载方法。

我们使用对单个的，相同的$ d $维状态的相同副本进行的测量来研究量子断层扫描和阴影断层扫描的问题。我们首先因Haah等人而重新审视已知的下限。 （2017年）在痕量距离上具有准确性$ \ epsilon $的量子断层扫描，当测量选择与先前观察到的结果无关（即它们是非适应性的）时。我们简要地证明了这一结果。当学习者使用具有恒定结果数量的测量值时，这会导致更强的下限。特别是，这严格确定了民间传说的最佳性``Pauli phymography''算法的样本复杂性。我们还得出了$ \ omega（r^2 d/\ epsilon^2）$和$ \ omega（r^2 d/\ epsilon^2）的新颖界限（ R^2 d^2/\ epsilon^2）$用于学习排名$ r $状态，分别使用任意和恒定的结果测量，在非适应性情况下。除了样本复杂性，对于学习量子的实际意义，是一种实际意义的资源状态是算法使用的不同测量值的数量。我们将下限扩展到学习者从固定的$ \ exp（o（d））$测量的情况下进行自适应测量的情况。这特别意味着适应性。没有使用可有效实现的单拷贝测量结果给我们任何优势。在目标是预测给定的可观察到给定序列的期望值的情况下，我们还获得了类似的界限，该任务被称为阴影层析成像。在适应性的情况下单拷贝测量可通过多项式大小的电路实现，我们证明了基于计算给定可观察物的样本平均值的直接策略是最佳的。

我们表明，具有“低稳定器复杂性”的量子状态可以有效地与HAAR随机区分开。具体而言，给定$ n $ qubit的纯状态$ | \ psi \ rangle $，我们给出了一种有效的算法，以区分$ | \ psi \ rangle $是（i）haar-random或（ii）具有稳定器保真度的状态至少$ \ frac {1} {k} $（即，具有一些稳定器状态的保真度至少$ \ frac {1} {k} $），保证就是其中之一。使用Black-box访问$ | \ psi \ rangle $，我们的算法使用$ o \！\ left（k^{12} \ log（1/\ delta）\ right）$ copies $ | \ psi \ rangle $和$ o \！\ left（n k^{12} \ log（1/\ delta）\ right）$ $时间以概率至少$ 1- \ delta $成功，并且随着访问状态准备统一，以$ | | \ psi \ rangle $（及其倒数），$ o \！\ left（k^{3} \ log（1/\ delta）\ right）$ queries和$ o \！\！ log（1/\ delta）\ right）$时间就足够了。作为推论，我们证明$ \ omega（\ log（n））$ $ t $ - 盖特对于任何Clifford+$ t $ circile都是必不可少的，以准备计算上的pseudorandom Quantum Quantum state，这是一种首要的下限。

机器学习被认为是量子计算最有前途的应用之一。因此，寻找机器学习模型的量子类似物的量子优势是一个关键的研究目标。在这里，我们表明，具有量子内核（QSVM）的变异量子分类器（VQC）和支持向量机可以基于K-相关问题解决分类问题，该问题已知是PromiseBQP complete。由于PromistBQP复杂度类包括所有有界的量子量子多项式时间（BQP）决策问题，因此我们的结果暗示存在特征图和量子内核，该量子内核使VQC和QSVM有效求解器用于任何BQP问题。这意味着可以设计VQC或QSVM的量子内核的特征图，以对任何在多项式时间内无法经典求解但与量子计算机相反的分类问题具有量子优势。

我们证明了能够在$ N $ -Qubit州$ \ Rho $同时的最多$ k $ reporicas上进行纠结的速度，有$ \ rho $的属性，这需要至少订购$ 2 ^ n / k^ 2 $测量学习。但是，相同的属性只需要一个测量来学习，如果我们可以在$ k，n $的k，n $的多个副本多项式上进行纠缠测量。因为上面保持每个正整数$ k $，我们获得了一系列的任务等级，需要有效地执行更多的副本。我们介绍了一种强大的证明技术来建立我们的结果，并用它来提供用于测试量子状态的混合的新界限。

变异贝叶斯（VB）是机器学习和统计数据中的关键方法，是贝叶斯深度学习最近成功的基础。天然梯度是有效VB估计的重要组成部分，但在高维度上的计算量非常昂贵。我们提出了一种基于计算有效回归的自然梯度估计方法，并根据标准假设提供了收敛的保证。该方法使使用量子矩阵倒置可以进一步加速VB。我们证明问题设置满足了量子矩阵反转所需的条件以实现计算效率。该方法可与广泛的统计模型一起使用，不需要特殊用途或简化的变异分布。

量子机学习（QML）中的内核方法最近引起了人们的重大关注，作为在数据分析中获得量子优势的潜在候选者。在其他有吸引力的属性中，当训练基于内核的模型时，可以保证由于训练格局的凸度而找到最佳模型的参数。但是，这是基于以下假设：量子内核可以从量子硬件有效获得。在这项工作中，我们从准确估计内核值所需的资源的角度研究了量子内核的训练性。我们表明，在某些条件下，可以将量子内核在不同输入数据上的值呈指数浓缩（在量子数中）指向一些固定值，从而导致成功训练所需的测量数量的指数缩放。我们确定了可以导致集中度的四个来源，包括：数据嵌入，全球测量，纠缠和噪声的表达性。对于每个来源，分析得出量子内核的相关浓度结合。最后，我们表明，在处理经典数据时，训练用内核比对方法嵌入的参数化数据也容易受到指数浓度的影响。我们的结果通过数值仿真来验证几个QML任务。总体而言，我们提供指南，表明应避免某些功能，以确保量子内核方法的有效评估和训练性。

由于在执行基本线性代数子程序（BLAS）时，大多数ML算法中的基本元素，量子机学习（QML）算法在机器学习（ML）域中获得了很大的相关性。通过利用BLAS操作，我们提出，实现和分析了$ \ MATHCAL {O}（NKLOG（D）I / C）$的低时间复杂度，以将其应用于读出读数鉴别量子态的根本问题。辨别量子状态允许识别量子状态$ | 0 \ rangle $和$ | 1 \ rangle从低级同步和正交信号（IQ）数据，并且可以使用自定义ml模型来完成。为了减少经典计算机的依赖性，我们使用Qk-means在IBMQ波哥大设备上执行状态辨别，并设法查找高达98.7％的分配保真度，其仅低于K-Means算法的分配保真。从将算法应用于量子状态的组合产生的分配保真度评分显示了使用Pearson相关系数的相关性分析，其中证据显示（1,2）和（2,3）邻近Qubit耦合的跨谈分析的装置。