2020年你所在的量子计算领域有哪些值得读的 paper？

今天心情好来填一下某上古大坑. 所有工作来源为 arXiv (不包括 ECCC 和 IACR ePrint), 时间从 2020 年 1 月 1 日到 2021 年 4 月 30 日. 列表仅代表个人喜好, 没有 quantum Shannon theory, 没有 NISQ/near-term, 也没有涉及 track B / PL theory; 有少量 algorithms 和 cryptography. 背景介绍一切从简, 有一些有补充链接. 空着的挖坑待填.

1. Quantum advantages vs. quantum hype

(1) The Argument against Quantum Computers, the Quantum Laws of Nature, and Google's Supremacy Claims

为信仰充值, 免受 quantum hype 荼毒.

(2) Quantum advantage for computations with limited space

Width-2 branching program 的 quantum advantage. 见 QIP 2021 有哪些值得关注的论文 ？ 中 124.

(3) Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits

见 QIP 2021 有哪些值得关注的论文 ？.

(4) Fast simulation of planar Clifford circuits

很精致的一个工作. 见 QIP 2021 有哪些值得关注的论文 ？ 中 116.

2. Complexity theory / Non-local games

(1) MIP*=RE / Quantum soundness of the classical low individual degree test

第一篇见 如何看待 MIP*=RE? 和 Climber.pI：量子交互式证明可以验证停机问题吗?.

第二篇见 有没有可能一个数学证明是错的，然而所有人都没注意到呢？.

(2) Quantum Logspace Algorithm for Powering Matrices with Bounded Norm / Eliminating Intermediate Measurements in Space-Bounded Quantum Computation

证明了 quantum logspace 的 deferred principle, 进而证明了 quantum logspace 是 well-defined. 见 QIP 2021 有哪些值得关注的论文 ？ 中 84:

• 前者观察到了只有 projection 的 intermediate measurement (即没有根据测量结果的 classical control), 其实相当于做 contraction (即 norm 不超过 1) matrix 的乘法 -- 于是可以把给定初态的 logspace circuit 在特定 basis 下的 measurement 的结果, 写成关于一系列 contraction matrix 的乘积的二次型的形式; 而计算这样的二次型, 其实类似知道起始角度的 Grover 算法.
• 后者的结果则强得多, 他们证明了常见的线性代数相关的 DET-complete 问题的 well-conditioned 版本都是 BQL-complete 的 (规约是 condition-number-preserving 的, 尽管是 case-by-case 的), 而一般的 quantum logspace circuit 可以写成某些矩阵问题.

(3) StoqMA meets distribution testing / StoqMA vs. MA: the power of error reduction

如果我们把 QMA 的 verifier 用到的 quantum circuit 限制成 Toffoli, CNOT, X 的话, 那么这样的复杂性类是 MA; 如果我们再把最后的 measurement 从 0/1 基 换成 +/- 基的话, 那么这样的复杂性类是 StoqMA. 这个复杂性最早是用于刻画 stoquastic Hamiltonian 的 local Hamiltonian problem 的, 可以证明它在 MA 和 AM 之间. 一个很自然的问题是, StoqMA 是否等于 MA?

第一篇指出 (1) StoqMA 的"优势"是来自 optimal witness 是 non-negative state (或者说概率分布), 而不是比特串; 同时证明了把 optimal witness 现在可以高效地计算每个权的态 (称为 easy witness) 的话, 这样的 eStoqMA 也在 MA 里, 从而可以很简单地证明 \mathsf{StoqMA}_1 在 MA 中. (2) StoqMA 关于 no case (soundness) 的 error reduction, 可以通过定义和一些巧妙但简单的构造给出. 第二篇则证明 StoqMA 关于 yes case (completeness) 的 error reduction 可以直接推出 StoqMA=MA.

(4) Bounds on the QAC$^0$ Complexity of Approximating Parity

Circuit complexity 中广为人知的一个结果是 Parity 不在 \mathsf{AC^0} 里, 这个基本结果一来导出了 \mathsf{AC^0} \not\subset \mathsf{NC^1}, 二来是后来著名的 switching lemma 的弱化版本. 但是相比之下, quantum circuit 的许多基本性质大家都不甚了解, 譬如说证明 Parity 不在 \mathsf{QAC}^0 里 (即使只是这个复杂性类的定义也不显然), 这篇工作令人惊喜地给出了部分答案.

(5) Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers

Ryan Williams 在 07 年证明了 NTIME[O(n)] 的某个 time-space lower bound (应该就是 O'Donnell 那门 CS Theory Toolkits 里举得那个例子). 这里证明 QCMATIME[O(n)] 不能被仅使用 sublinear space 的某个多项式时间计算模拟; 并且还证明了 MATIME[O(n)] 和 QCMATIME[O(n)] 关于 logspace 也有类似的结果 (当然多项式的次数不一样).

这里的证明技术称作 quantifier-trading proofs, 就是更精细的 polynomial hierarchy, 即量词后的变量是某个具体多项式长度的. 有两种方式, 一个是 speedup rule, 通过添加更多量词来减少时间; 一个是 slowdown rule, 即通过一些假设移走量词 (但是增加时间). 结合两者用类似 time-hierarchy theorem 推出矛盾, 从而推翻假设证明 circuit lower bound. 这篇文章比较巧妙地用 Grover algorithm 加速了 forall quantifier 的 slowdown rule.

(6) 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time

Commuting-operator model 下的 non-local games. 见 QIP 2021 有哪些值得关注的论文 ？ 中 127.

(7) The membership problem for constant-sized quantum correlations is undecidable

见 QIP 2021 有哪些值得关注的论文 ？.

(8) A Parallel Repetition Theorem for the GHZ Game

见 QIP 2021 有哪些值得关注的论文 ？ 中 378.

3. Query / Communication complexity

(1) Symmetry and Quantum Query-to-Communication Simulation

(2) On Query-to-Communication Lifting for Adversary Bounds

(3) Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem

Total Boolean functions 的查询复杂度下界.

(4) An Optimal Separation of Randomized and Quantum Query Complexity / $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity

(5) A Direct Product Theorem for One-Way Quantum Communication

(6) Symmetries, graph properties, and quantum speedups

Partial Boolean functions 中的有一些的查询复杂度有超多项式加速 (譬如 Simons 算法的对应), 那么我们能找到其中哪些有或者没有超多项式加速呢? Aaronson 和 Ambainis 在 09 年给出关于 symmetric (partial) Boolean functions 的否定答案, 即仅有多项式加速 R(f)=\tilde{O}(Q^7(f)). 鉴于 Grover 算法告诉我们, total Boolean functions 的查询复杂度不难有平方加速, 那么超平方加速看起来仍然是有趣的 -- Chailloux 在 18 年给出了很简短的证明, 将 symmetric functions 加速上限改进到立方. 本文则推广了上述结果, 考虑关于图的 symmetry, 并给出了某些子类 (如 glued tree) 有超多项式加速; 有趣的是, 加速的存在与否跟图的表示方法 (诸如邻接矩阵或邻接表) 也有关.

4. Learning theory

(1) Improved quantum data analysis / The Quantum Union Bound made easy

问题介绍见去年的回答中关于 Shadow Estimation 的部分: 2019 年你所在的量子计算领域有哪些值得读的 paper？. 第一篇对 Aaronson-Rothblum 的冗长 paper 抽丝剥茧, 指出 Shadow Estimation 是 Adaptive Data Analysis 的量子对应; 并给出了 Shadow Estimation 和 Full-State Tomography 之间的联系. 当然, 最精彩的地方是他们在一些情形下改进了 gentle measurement / quantum union bound, 证明了在 threshold 附近对误差不太敏感的版本 (就是一个经典概率论结果), 然后"提升"回量子情形.

第二篇是 quantum union bound 的简化证明, 很短但又很多直觉解释. \

(2) Predicting Many Properties of a Quantum System from Very Few Measurements / Efficient estimation of Pauli observables by derandomization

见去年的回答中关于 Shadow Estimation 的部分: 2019 年你所在的量子计算领域有哪些值得读的 paper？. 第一篇增加了更多的应用. 第二篇则是把第一篇中用到的 Union bound+Chernoff bound 用 multiplicative weight update 来 derandomization.

(3) Quantum Coupon Collector

很精致的工作. Coupon collection 是概率方法入门课常见例子之一, 如果只收集一部分 coupon 的话, 这可以看成一个 PAC learning 问题 (对应的 concept class 的 VC dimension 是 1). 对于 classical PAC, 这个例子在 improper learning 需要 n 个 samples, 但是 proper learning 却需要 n log n samples. 而对于 quantum PAC, 这样的 separation 对这个例子并不存在.

更进一步的猜想是 proper learning 和 improper learning 关于 sample complexity 的 separation 对 quantum PAC learning 并不存在.

(4) Private learning implies quantum stability

(5) On the Hardness of PAC-learning stabilizer States with Noise

(6) Information-theoretic bounds on quantum advantage in machine learning

(7) Entanglement is Necessary for Optimal Quantum Property Testing

5. Error correction codes and fault-tolerant quantum objects

(1) Balanced Product Quantum Codes / Quantum LDPC Codes with Almost Linear Minimum Distance / Fiber Bundle Codes: Breaking the $N^{1/2} \operatorname{polylog}(N)$ Barrier for Quantum LDPC Codes

以上三篇见 如何看待 Hastings、Haah 和 O'Donnell 关于量子 LDPC 编码的新进展？ 和 如何看待 2020 下半年关于量子 LDPC 的一系列新进展？.

(2) Constructing quantum codes from any classical code and their embedding in ground space of local Hamiltonians

见 QIP 2021 有哪些值得关注的论文 ？.

(3) Fault-tolerant Coding for Quantum Communication

见 QIP 2021 有哪些值得关注的论文 ？.

6. Algorithms

(1) Quantum algorithm for nonlinear differential equations / Efficient quantum algorithm for dissipative nonlinear differential equations

尽管 linear ODE 是 BQP-complete 的 (可以设法使用 HHL 算法求解), 而此前对 T-step 时间演化的 quadratic ODE, 都只有关于 T 的指数的算法. 这些工作降对 T 的依赖大幅改进到了多项式.

(2) Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra

(3) Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems

(4) Near-optimal ground state preparation

quantum singular value transforms 的应用.

(5) Distributed Quantum Proofs for Replicated Data

7. Physics-motivated problems

(1) An area law for 2D frustration-free spin systems

QIP 2022 Plenary Talk 预订. 见 Area law (面积定律) 到底意味着什么性质？.

(2) Sample-efficient learning of quantum many-body systems

见 QIP 2021 有哪些值得关注的论文 ？ 中 54.

(3) The importance of the spectral gap in estimating ground-state energies

典型的 Hamiltonian complexity 工作, 但是又有一些物理相关的 insights. 见 QIP 2021 有哪些值得关注的论文 ？中 392.

(4) Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states

见 QIP 2021 有哪些值得关注的论文 ？ 中 35.

(5) Tensor Networks contraction and the Belief Propagation algorithm

很有意思的想法, 用 neural network 中的 belief propogation 来做张量网络的 contraction; 最奇妙的时候还能找到严格的数学对应. 那么很自然地要问, 这样的想法能不能启发出更有效的张量网络的收缩算法.

(6) Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems

张量网络主要技术 (MPS/PEPS) 提出者们的综述, 看起来是 Rev. Mod. Phys. 约稿.

(7) On the Hardness of Detecting Macroscopic Superpositions

唯一一篇直觉学派的工作, 他们把 Susskind 的某个猜想修改成了正确的形式, 并且证明了出来.

8. CS Theory in general

(1) Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

背景介绍见 Pseudorandom Generator (PRG) 有哪些有趣的(算法)应用？. 就是说 PRG 可以定义在某些 circuit family 上, 而定义在 linear threshold functions 上的 PRG 可以近似地看做某种量化版本的中心极限定理 (即 Berry-Esseen theorem), 这被 Boolean function community 的人称作 invariance principle. 而从凸几何的观点看, linear threshold functions 正好定义了一个 halfspace, 于是很自然地就会问 polytope 甚至 spectrahedron 有没有类似的结果. 这篇建立了 positive spectrahedron 的类似结果.

(2) Bipartite Perfect Matching as a Real Polynomial / The Dual Polynomial of Bipartite Perfect Matching

(3) Barriers for rectangular matrix multiplication

(4) From Holant to Quantum Entanglement and Back

Exact counting 和 quantum Shannon theory 的一点联系.

9. Cryptography

(1) Oblivious Transfer is in MiniQCrypt / One-Way Functions Imply Secure Computation in a Quantum World

难得发现的量子密码学的独特现象. 见 QIP 2021 有哪些值得关注的论文 ？ 中 176.

(2) Continuous LWE

LWE 跟 adversary samples 的新联系. 譬如说给定若干层 (足够多) 的 high-dimension data, 能不能找到某个 hidden direction 做 classification; 如果这个问题有多项式时间算法的话, 就可以推出 lattice problems 有多项式时间算法.

(3) Scalable Pseudorandom Quantum States

前两年那篇 pseudorandom quantum state 的升级版本, 把之前用到的 field 改进到和其他参数无关的 binary field, 因而变成 scalable 的.

(4) Succinct Blind Quantum Computation Using a Random Oracle

Cryptographic quantum delegation 的新作.

(5) Post-Quantum Succinct Arguments

Killian 在 1992 年用 PCP theorem 和 collision-resistent hash function 给了非常简单一个 NP 的 succinct argument. 那么这个简单的构造是否是 quantum-safe 的呢? 这个工作给了肯定答案, 证明技术是改进过的 quantum rewinding (类似技术有很多个名字, 比如说 Marriott-Watrous / Jordan lemma / gentle measurement / quantum OR bound; 这些看起来很像的 primitive 有一些细微的差别).

这不是镜像问题。。这是套娃问题。。

首先是万年安利 scirate 时间：

两位数及以上的 scites 基本可以一看（虽然scite不代表论文水平）

安利完成（1/1）

作为提了 2019 年那个问题的人来加速一下问题被答流程...基于个人能力和摸鱼程度只包括主动关注过、至少看过 talk 或 paper （但并不一定完全了解）的一些工作，不包括 2019 年值得读的 paper 中出现过的post于 2020 年的 paper，不包括 QIP 2021 值得关注的论文，不包括值得读但我并没有读的 paper，可能包括一些发表于 2020 年但在 2019 年已经 post 的 paper。限于个人兴趣100%不包括偏实验/软件/物理/QML(主要指NISQ+VQE)向的工作，考虑心情暂时不包括大部分FTQC的工作。

基本不介绍问题背景和主要结果，目前所有可能有的介绍均处于待填状态。

Quantum algorithms

1. Andris Ambainis, Nikita Larka Quantum algorithms for computational geometry problems

Complexity

1. Tony Metger, Thomas Vidick Self-testing of a single quantum device under computational assumptions
2. Justin Holmgren, Ran Raz A Parallel Repetition Theorem for the GHZ Game
3. Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani Efficiently generating ground states is hard for postselected quantum computation
4. Anurag Anshu, David Gosset, Karen Morenz Beyond product state approximations for a quantum analogue of Max Cut
5. Lin Lin, Yu Tong Near-optimal ground state preparation
6. Yupan Liu StoqMA meets distribution testing

Learning theory & tomography

1. Matthew Coudron, Sanketh Menda Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
2. Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai On the Need for Large Quantum Depth
3. Nengkun Yu Sample efficient tomography via Pauli Measurements
4. Alexandru Gheorghiu, Matty J. Hoban Estimating the entropy of shallow circuit outputs is hard
5. Costin Bădescu, Ryan O'Donnell Improved quantum data analysis

Quantum error correction

1. Nicolas Delfosse, Ben W. Reichardt, Krysta M. Svore Beyond single-shot fault-tolerant quantum error correction
2. 如何看待 2020 下半年关于量子 LDPC 的一系列新进展？ 见问题描述和可能会有但目前还没有的回答

其他

1. Aram Harrow: Small quantum computers and large classical data sets
2. Sebastien Bubeck, Sitan Chen, Jerry Li Entanglement is Necessary for Optimal Quantum Property Testing
3. Arjan Cornelissen, Stacey Jeffery, Maris Ozols, Alvaro Piedrafita Span programs and quantum time complexity
4. Kyle Burke, Matthew Ferland, Shang-Hua Teng Quantum Combinatorial Games: Structures and Computational Complexity