Manuscript

Bounded Relative Boundary Implies Narrow DNF Approximation
Friedgut conjectured that an increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated …
Chenghua Liu, Boning Meng
PDF 引用 arXiv
Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation
The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = O\left( \alpha T + …
Boyang Chen, Minbo Gao, Zhengfeng Ji, Tongyang Li, Xinzhao Wang, Shuo Zhou
PDF 引用 arXiv
Quantum Pessiland
Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all …
Boyang Chen, Tomoyuki Morimae, Takashi Yamakawa
PDF 引用 arXiv
Lifting connectivity bottlenecks in superconducting quantum processors via enriched native two-qubit gates
Limited qubit connectivity is a central architectural constraint in superconducting quantum processors, whose planar layouts require …
Hanyi Wang, Jingzhe Guo, Lijun Sun, Zhaohui Yang, Weizhi Tao, Xingye Yuan, Qiankun Wang, Bihao Guo, Chunwang Liu, Rui Yang, Yang Li, Yu Fan, Jiasheng Hu, Junhe Wang, Shuyue Zheng, Shengbin Wang, Xinfang Zhang, Feng Wu, Hantao Sun, Jianxin Chen
PDF 引用 arXiv
Lower Bounds for Domination-Type Problems Parameterized by Rank-Width
For graphs of rank-width (w), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed …
Chenghua Liu, Boning Meng
PDF 引用 arXiv
Depth Enables Local Entropy: Quadratic Depth Dependence in Deep Variation-Norm ReLU Regression
We study Gaussian regression over the explicit vector-valued Parhi–Nowak deep-RBV^2 architecture with depth L, width w, layer-sum …
Tao Jiang, Minbo Gao, Shaowei Cai
PDF 引用 arXiv
Unclonable encryption from BB84 states: a simultaneous Goldreich-Levin reduction
Goldreich-Levin reductions are ubiquitous in cryptography: they convert an algorithm capable of guessing $\langle r, m \rangle$ (mod …
Andrea Coladangelo, Qipeng Liu, Ziyi Xie
PDF 引用 arXiv
From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
In a landmark JACM paper recognized with the 2021 G{ö}del Prize, Cai and Chen established a complete complexity dichotomy for counting …
Chenghua Liu, Boning Meng
PDF 引用 arXiv
Quantum Speedups for Log-Concave Sampling from Local Structure
For a convex function $f \colon \mathbb{R}^d \to \mathbb{R}$, the problem of sampling from a distribution proportional to $e^{-f(x)}$ …
Chenghua Liu, Qisheng Wang, Zhengfeng Ji
PDF 引用 arXiv
Efficient Compilation for Hamiltonian Simulation via Global Binary Symplectic Form Simplification
Hamiltonian simulation is a core quantum workload, underpinning variational quantum algorithms and Trotterized time evolution. Such …
Zhaohui Yang, Yuwei Han, Ruiyun Zhang, Dawei Ding, Jianxin Chen, Yuan Feng, Yuan Xie
PDF 引用 arXiv