Changpeng Shao

We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model (``OR queries''), the oracle returns whether a given subset of the vertices contains any edges. In the second (``parity queries''), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al.\ for a ``gapped" version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.

We investigate Lindbladian fast-forwarding and its applications to estimating Gibbs state properties. Fast-forwarding refers to the ability to simulate a system of time $t$ using significantly fewer than $t$ queries or circuit depth. While various Hamiltonian systems are known to circumvent the no fast-forwarding theorem, analogous results for dissipative dynamics, governed by Lindbladians, remain largely unexplored. We first present a quantum algorithm for simulating purely dissipative Lindbladians with unitary jump operators, achieving additive query complexity $ \mathcal{O}\left(t + \frac{\log(\varepsilon^{-1})}{\log\log(\varepsilon^{-1})}\right)$ up to error~$\varepsilon$, improving previous algorithms. When the jump operators have certain structures (i.e., block-diagonal Paulis), the algorithm can be modified to achieve exponential fast-forwarding, attaining circuit depth $\mathcal{O}\left(\log\left(t + \frac{\log(\varepsilon^{-1})}{\log\log(\varepsilon^{-1})}\right)\right)$, while preserving query complexity. Using these fast-forwarding techniques, we develop a quantum algorithm for estimating Gibbs state properties of the form $\langle \psi_1 | e^{-\beta(H + I)} | \psi_2 \rangle$, up to additive error $\epsilon$, with $H$ the Hamiltonian and $\beta$ the inverse temperature. For input states exhibiting certain coherence conditions ---e.g.,~$\langle 0|^{\otimes n} e^{-\beta(H + I)} |+\rangle^{\otimes n}$---our method achieves exponential improvement in complexity (measured by circuit depth), $\mathcal{O} (2^{-n/2} \epsilon^{-1} \log \beta ),$ compared to the quantum singular value transformation-based approach, with complexity $\tilde{\mathcal{O}} (\epsilon^{-1} \sqrt{\beta} )$. We show how to apply this exponential improvement to applications such as the ground state overlap testing and amplitude estimation. For general $| \psi_1 \rangle$ and $| \psi_2 \rangle$, we also show how the level of improvement is changed with the coherence resource in $| \psi_1 \rangle$ and $| \psi_2 \rangle$.

We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms and serves as the foundation for new ones. Existing implementations of QSVT rely on block encoding, incurring an intrinsic $O(\log L)$ ancilla overhead and circuit depth $\widetilde{O}(L d\lambda )$ for polynomial transformations of a Hamiltonian $H=\sum_{k=1}^L H_k$, where $d$ is the polynomial degree and $\lambda=\sum_{k}\|H_k\|$. We introduce a simple yet powerful approach that utilizes only basic Hamiltonian simulation techniques, namely, Trotter methods, to: (i) eliminate the need for block encoding, (ii) reduce the ancilla overhead to only a single qubit, and (iii) still maintain near-optimal complexity. Our method achieves a circuit depth of $\widetilde{O}(L(d\lambda_{\mathrm{comm}})^{1+o(1)})$, without requiring any complicated multi-qubit controlled gates. Moreover, $\lambda_{\mathrm{comm}}$ depends on the nested commutators of the terms of $H$ and can be substantially smaller than $\lambda$ for many physically relevant Hamiltonians, a feature absent in standard QSVT. To achieve these results, we make use of Richardson extrapolation in a novel way, systematically eliminating errors in any interleaved sequence of arbitrary unitaries and Hamiltonian evolution operators, thereby establishing a general framework that encompasses QSVT but is more broadly applicable. We further design two randomized algorithms for QSVT in settings with only sampling access to the Hamiltonian terms. The first is a direct randomization of standard QSVT, while the second integrates qDRIFT within our interleaved-circuit architecture. Both achieve a complexity quadratic in $d$, which we establish as a lower bound for any randomized method implementing polynomial transformations in this model. Finally, as applications, we develop end-to-end quantum algorithms for solving linear systems and estimating ground state properties of Hamiltonians, both achieving near-optimal complexity without relying on oracular access. Overall, our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance, with implications for both near-term and fault-tolerant quantum computing.