24 papers
Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning
Vaneet Aggarwal
We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversaria…
A Sharp Local-Question Threshold for GHZ-Equatorial Completeness in Four-Player XOR Games
Ziao Tang, Chengkai Zhu, Ge Bai +2
We determine the smallest number of active questions per player at which a four-player binary exclusive-or (XOR) game of commuting-operator value one need not admit a Greenberger--…
Realified tensor networks: quantum circuit simulation on real-valued matrix accelerators
Yusheng Zhao, Xiwei Pan, Enji Xiong +2
Tensor-network contraction simulates quantum circuits, but modern matrix accelerators (NPUs, TPUs) expose only real GEMM pipelines, so the complex networks of quantum simulation mu…
Quantum Incapacity beyond No-Cloning and PPT Mechanisms
Chengkai Zhu, Xin Wang
We show an explicit qutrit channel whose private and quantum capacities both vanish, although it is neither antidegradable nor positive under partial transposition (PPT). This reso…
Benchmarking Agents for Proving Theorems in Quantum Algorithms and Quantum Information
Lei Zhang, Yusheng Zhao, Yimeng Cao +10
Formal verification is becoming increasingly practical for quantum computing, yet the ability of AI agents to construct machine-checkable proofs in this domain remains unmeasured.…
Lean-QIT: Towards a Formal Infrastructure for Quantum Information Theory
Chengkai Zhu, Ziao Tang, Guocheng Zhen +6
Quantum information theory (QIT) characterizes the capabilities and fundamental limits of quantum information processing, underpinning quantum communication, computation, and error…