惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

F
Fortinet All Blogs
爱范儿
爱范儿
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
B
Blog
WordPress大学
WordPress大学
Jina AI
Jina AI
GbyAI
GbyAI
aimingoo的专栏
aimingoo的专栏
N
Netflix TechBlog - Medium
腾讯CDC
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
阮一峰的网络日志
阮一峰的网络日志
The GitHub Blog
The GitHub Blog
V
Visual Studio Blog
Google DeepMind News
Google DeepMind News
月光博客
月光博客
博客园 - Franky
Y
Y Combinator Blog
MyScale Blog
MyScale Blog
大猫的无限游戏
大猫的无限游戏
Martin Fowler
Martin Fowler
雷峰网
雷峰网
小众软件
小众软件
H
Hackread – Cybersecurity News, Data Breaches, AI and More

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
An optimal tradeoff between entanglement and copy complex...
Sitan Chen, Jerry Li, Allen Liu · 2024-02-26 · via cs.DS updates on arXiv.org

There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between looks like. In this work, we study tomography in the natural setting where one can make measurements of $t$ copies at a time. For sufficiently small $ε$, we show that for any $t \le d^2$, $\widetildeΘ(\frac{d^3}{\sqrt{t}ε^2})$ copies are necessary and sufficient to learn an unknown $d$-dimensional state $ρ$ to trace distance $ε$. This gives a smooth and optimal interpolation between the known rates for single-copy and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at $t = 2$. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently biased and thus precludes naive batching approaches. Instead, we devise a novel two-stage procedure that uses Keyl's algorithm to refine a crude estimate for $ρ$ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of $ρ$, but to estimate the deviation of $ρ$ from the maximally mixed state. When $ρ$ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where $ρ$ is close to maximally mixed.