7 papers
Conditional dependence and Scrooge ensembles in shallow random quantum circuits
Yinchen Liu, Max McGinley, Thomas Schuster +1
The output state of a 2D geometrically local shallow random quantum circuit does not have long range correlations due to its lightcone structure. But this changes if one measures a…
Efficient quantum algorithm for Heisenberg spin systems
Sergey Bravyi, David Gosset, Yinchen Liu +1
The paper proves a lower bound on the spectral gap of a broad class of Heisenberg spin Hamiltonians and uses this to design an efficient quantum adiabatic algorithm for estimating…
Path-Minimality of -Energy for Connected Graphs
Yinchen Liu, Quanyu Tang
Let be a simple connected graph on vertices, and let be the eigenvalues of its adjacency matrix . For , define the -energy of…
On the Complexity of the Circuit Width Problem
Zhengfeng Ji, Yinchen Liu, Zhe'ou Zhou
Montanaro's polynomial representation expresses amplitudes of quantum circuits over the gates , , , and as normalized gaps of degree-three polynomials over $\mathbb…
Sample-efficient benchmarking of shallow all-to-all random quantum circuits
Gregory Bentsen, Bill Fefferman, Soumik Ghosh +2
Random circuit sampling (RCS) remains one of the most competitive frameworks for demonstrating quantum advantage in near-term noisy intermediate-scale quantum (NISQ) hardware. Unfo…
Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
Cheng Jiang, Yinchen Liu, Huacheng Yu
A fundamental question in streaming complexity is whether every space-efficient turnstile algorithm is implicitly a linear sketch. The landmark work of Li, Nguyen, and Woodruff [LN…