27 citations · 33 across the 18 of their papers we have counts for
18 papers
The -Conjecture for CIS -Graphs
Yinchen Liu, Quanyu Tang
We prove the -conjecture, which dates back to Gurvich's 1978 thesis. Specifically, let the edges of a complete graph be colored with colors , and for each let $G…
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…
A positive square-energy strengthening of Turán's theorem
Yinchen Liu, Quanyu Tang, Shengtong Zhang
Let be an -vertex graph with clique number , and let denote the sum of the squared positive adjacency eigenvalues. We prove that $$ \sqrt{s^+(G)}\le\left(1-\f…
The positive and negative square-energy conjecture
Yinchen Liu, Quanyu Tang, Shengtong Zhang
Let and denote the sums of the squares of the positive and negative adjacency eigenvalues of a graph , respectively. We prove the conjecture of Elphick, Farber…
Efficient quantum algorithm for Heisenberg spin systems
Sergey Bravyi, David Gosset, Yinchen Liu +1
We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet…
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 $G…
Path-Minimality for Positive -Energies, Laplacian-Type Spectra, and Line Graphs
Yinchen Liu, Quanyu Tang
We derive several applications of the path-minimality theorem for adjacency -energy proved in the companion paper. First, we prove the sharp inequality $$ \mathcal E_p^+(G)\ge \…
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…
Lee-Yang tensors and Hamiltonian complexity
Benjamin Wong, Sergey Bravyi, David Gosset +1
A complex tensor with binary indices can be identified with a multilinear polynomial in complex variables. We say it is a Lee-Yang tensor with radius if the polynomial…
On the complexity of sampling from shallow Brownian circuits
Gregory Bentsen, Bill Fefferman, Soumik Ghosh +2
While many statistical properties of deep random quantum circuits can be deduced, often rigorously and other times heuristically, by an approximation to global Haar-random unitarie…
On a conjecture of Nikiforov concerning the minimal -energy of connected graphs
Quanyu Tang, Yinchen Liu, Wei Wang
For a given simple graph \( G \), the \( p \)-energy of \( G \), denoted by \( \mathcal{E}_p(G) \), is defined as the sum of the \( p \)-th power of the absolute values of the eige…
On the Positive and Negative -Energies of Graphs under Edge Addition
Quanyu Tang, Yinchen Liu, Wei Wang
In this paper, we introduce the concepts of positive and negative -energies of graphs and investigate their behavior under edge addition. Specifically, we generalize the classic…
Quantum advantage from measurement-induced entanglement in random shallow circuits
Adam Bene Watts, David Gosset, Yinchen Liu +1
We study random constant-depth quantum circuits in a two-dimensional architecture. While these circuits only produce entanglement between nearby qubits on the lattice, long-range e…
Classical simulation of peaked shallow quantum circuits
Sergey Bravyi, David Gosset, Yinchen Liu
An -qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of . We describe a classical algorith…
A rapidly mixing Markov chain from any gapped quantum many-body system
Sergey Bravyi, Giuseppe Carleo, David Gosset +1
We consider the computational task of sampling a bit string from a distribution , where is the unique ground state of a local Hamiltonian .…
How to simulate quantum measurement without computing marginals
Sergey Bravyi, David Gosset, Yinchen Liu
We describe and analyze algorithms for classically simulating measurement of an -qubit quantum state in the standard basis, that is, sampling a bit string from the proba…