Source author record

Yechao Zhu

Yechao Zhu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

quant-ph Computational Complexity Data Structures and Algorithms hep-th Information Theory math.IT

Catalog footprint

What is connected

4works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Doubly infinite separation of quantum information and communication

We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call "doubly infinite," between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)] for which there exist instances where the quantum information complexity tends to zero as the size of the input $n$ increases. By showing that the quantum communication complexity of these games scales at least logarithmically in $n$, we obtain our result. We further show that the established lower bounds and gaps still hold even if we allow a small probability of error. However in this case, the $n$-qubit quantum message of the zero-error strategy can be compressed polynomially.

preprint2016arXiv

Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree

We consider constraint satisfaction problems of bounded degree, with a good notion of "typicality", e.g. the negation of the variables in each constraint is taken independently at random. Using the quantum approximate optimization algorithm (QAOA), we show that $ μ+Ω(1/\sqrt{D}) $ fraction of the constraints can be satisfied for typical instances, with the assignment efficiently produced by QAOA. We do so by showing that the averaged fraction of constraints being satisfied is $ μ+Ω(1/\sqrt{D}) $, with small variance. Here $ μ$ is the fraction that would be satisfied by a uniformly random assignment, and $ D $ is the number of constraints that each variable can appear. CSPs with typicality include Max-$ k $XOR and Max-$ k $SAT. We point out how it can be applied to determine the typical ground-state energy of some local Hamiltonians. We also give a similar result for instances with "no overlapping constraints", using the quantum algorithm. We sketch how the classical algorithm might achieve some partial result.

preprint2015arXiv

Holographic Trace Anomaly and Local Renormalization Group

The Hamilton-Jacobi method in holography has produced important results both at a renormalization group (RG) fixed point and away from it. In this paper we use the Hamilton-Jacobi method to compute the holographic trace anomaly for four- and six-dimensional boundary conformal field theories (CFTs), assuming higher-derivative gravity and interactions of scalar fields in the bulk. The scalar field contributions to the anomaly appear in CFTs with exactly marginal operators. Moving away from the fixed point, we show that the Hamilton-Jacobi formalism provides a deep connection between the holographic and the local RG. We derive the local RG equation holographically, and verify explicitly that it satisfies Weyl consistency conditions stemming from the commutativity of Weyl scalings. We also consider massive scalar fields in the bulk corresponding to boundary relevant operators, and comment on their effects to the local RG equation.

preprint2012arXiv

Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates

We study the quantum query complexity of constant-sized subgraph containment. Such problems include determining whether an $ n $-vertex graph contains a triangle, clique or star of some size. For a general subgraph $ H $ with $ k $ vertices, we show that $ H $ containment can be solved with quantum query complexity $ O(n^{2-\frac{2}{k}-g(H)}) $, with $ g(H) $ a strictly positive function of $ H $. This is better than $ \tilde{O}\s{n^{2-2/k}} $ by Magniez et al. These results are obtained in the learning graph model of Belovs.