6 papers
Triangle Criterion: a mixed-state magic criterion with applications in distillation and detection
Zhenhuan Liu, Tobias Haug, Qi Ye +2
We introduce a mixed-state magic criterion, the Triangle Criterion, which plays a role for magic analogous to the Positive Partial Transposition (PPT) Criterion for entanglement: i…
Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs
Zhen-Peng Xu, Jie Wang, Qi Ye +3
A set of Pauli stings is well characterized by the graph that encodes its commutatitivity structure, i.e., by its frustration graph. This graph provides a natural interface between…
Deliberation via Matching
Kamesh Munagala, Qilin Ye, Ian Zhang
We study deliberative social choice, where voters engage in small-group discussions to output collective preferences that are then aggregated by a social choice rule. We introduce…
Transformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data
Qilin Ye, Deqing Fu, Robin Jia +1
Transformers often fail to learn generalizable algorithms, instead relying on brittle heuristics. Using graph connectivity as a testbed, we explain this phenomenon both theoretical…
Ansatz-free Hamiltonian learning with Heisenberg-limited scaling
Hong-Ye Hu, Muzhou Ma, Weiyuan Gong +4
Learning the unknown interactions that govern a quantum system is crucial for quantum information processing, device benchmarking, and quantum sensing. The problem, known as Hamilt…
On the sample complexity of purity and inner product estimation
Weiyuan Gong, Jonas Haferkamp, Qi Ye +1
We study the sample complexity of the prototypical tasks quantum purity estimation and quantum inner product estimation. In purity estimation, we are to estimate of an un…