Qisheng Wang

Uhlmann's theorem is a central result in quantum information theory, associating the closeness of two quantum states with that of their purifications. This theorem well characterizes the fundamental task of transforming a quantum state into another state via local operations on its subsystem. The optimal transformation for this task is called the Uhlmann transformation, which has broad applications in various fields; however, its quantum circuit implementation and computational cost have remained unclear. In this work, we fill this gap by proposing quantum query and sample algorithms that realize the Uhlmann transformation in the form of quantum circuits. These algorithms achieve exponential improvements in computational costs, including query and sample complexities, over naive approaches based on state measurements such as quantum state tomography, under certain computational models. We apply our algorithms to the square root fidelity estimation task and particularly show that our approach attains a better query complexity than the prior state-of-the-art. Furthermore, we discuss applications to several information-theoretic tasks, specifically, entanglement transmission, quantum state merging, and algorithmic implementation of the Petz recovery map, providing a comprehensive evaluation of the computational costs.

Estimating nonlinear properties of quantum states, particularly observable-weighted moments $\mathrm{Tr}(\mathcal{O}\rho^k)$, is a central task in quantum information science. In this work, we present a unified framework establishing the optimal sample complexity for this task and a resource-efficient protocol for its implementation. Theoretically, we prove that $\tilde{\Theta}(k)$ samples of an $m$-qubit state $\rho$ are sufficient and necessary to \textit{simultaneously} estimate the full hierarchy of moments $\mathrm{Tr}(\mathcal{O}\rho), \dots, \mathrm{Tr}(\mathcal{O}\rho^k)$. This reveals that estimating the entire hierarchy is asymptotically as efficient as estimating the single highest-order term. To realize this, we introduce a circuit architecture leveraging qubit reuse that requires only $2m+1$ physical qubits and $\mathcal{O}(k)$ depth. This approach achieves the near-optimal sample complexity of $\mathcal{O}(k \log k / \varepsilon^2)$ with significantly reduced hardware overhead. We demonstrate the framework's utility by bounding maximum eigenvalues, performing virtual cooling on the Heisenberg model, and experimentally measuring higher-order Rényi entropies on a superconducting processor.

Rare events, though infrequent, can have significant impacts across various domains. We present a quantum algorithm for efficiently sampling rare events from stochastic processes. Our algorithm constructs quantum sample states that superpose only rare events, defined as those occurring with probability below a threshold \(\Delta\). The algorithm consists of three key steps: (1) constructing an amplitude block encoding from the quantum sample state of the original process, (2) implementing quantum singular value transformation of a polynomial approximation of a thresholding function, and (3) performing measurement and post-selection. For sufficiently large sequence lengths, we prove that our algorithm achieves a quadratic speedup over classical methods, requiring only \(\Theta(1/\sqrt{\Delta})\) queries to prepare an even superposition over rare events, compared to the classical \(\mathcal{O}(1/\Delta)\) complexity. We demonstrate our algorithm's effectiveness through numerical simulations on the Dyson-Ising chain, showing successful identification and amplification of rare events while suppressing non-rare events.

The complexity class Quantum Statistical Zero-Knowledge (𝖰𝖲𝖹𝖪), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound 𝖰𝖨𝖯(𝟤)∩co-𝖰𝖨𝖯(𝟤), which was simplified following the inclusion 𝖰𝖨𝖯(𝟤)⊆𝖯𝖲𝖯𝖠𝖢𝖤 established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, 𝖰𝖨𝖯(𝟤) denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and co-𝖰𝖨𝖯(𝟤) denotes the complement of 𝖰𝖨𝖯(𝟤). We slightly improve this upper bound to 𝖰𝖨𝖯(𝟤)∩co-𝖰𝖨𝖯(𝟤) with a quantum linear-space honest prover. A similar improvement also applies to the upper bound for the non-interactive variant 𝖭𝖨𝖰𝖲𝖹𝖪. Our main techniques are an algorithmic version of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).

The relative entropy between quantum states quantifies their distinguishability. The estimation of certain relative entropies has been investigated in the literature, e.g., the von Neumann relative entropy and sandwiched R{\'e}nyi relative entropy. In this paper, we present a comprehensive study of the estimation of the quantum Tsallis relative entropy. We show that for any constant $\alpha \in (0, 1)$, the $\alpha$-Tsallis relative entropy between two quantum states of rank $r$ can be estimated with sample complexity $\operatorname{poly}(r)$, which can be made more efficient if we know their state-preparation circuits. As an application, we obtain an approach to tolerant quantum state certification with respect to the quantum Hellinger distance with sample complexity $\widetilde{O}(r^{3.5})$, which \textit{exponentially} outperforms the folklore approach based on quantum state tomography when $r$ is polynomial in the number of qubits. In addition, we show that the quantum state distinguishability problems with respect to the quantum $\alpha$-Tsallis relative entropy and quantum Hellinger distance are $\mathsf{QSZK}$-complete in a certain regime, and they are $\mathsf{BQP}$-complete in the low-rank case.