Kaito Wada

Achieving quantum advantage in efficiently estimating collective properties of quantum many-body systems remains a fundamental goal in quantum computing. While the quantum gradient estimation (QGE) algorithm has been shown to achieve doubly quantum enhancement in the precision and the number of observables, it remains unclear whether one benefits in practical applications. In this work, we present a generalized framework of the adaptive QGE algorithm, and further propose two variants which enable us to estimate the collective properties of fermionic systems using the smallest cost among existing quantum algorithms. The first method utilizes the symmetry inherent in the target state, and the second method enables estimation in a single-shot manner using the parallel scheme. We show that our proposal offers a quadratic speedup compared with prior QGE algorithms in the task of fermionic partial tomography for systems with limited particle numbers. Furthermore, we provide numerical demonstrations that, for a problem of estimating fermionic 2-RDMs, our proposals improve the number of queries to the target state preparation oracle by a factor of 4.4 for the nitrogenase FeMo cofactor and by a factor of 7.8 for Fermi-Hubbard model of 200 sites in chemical accuracy.

Density matrix exponentiation (DME) is a general procedure that converts an unknown quantum state into the Hamiltonian evolution. This enables state-dependent operations and can reveal nontrivial properties of the state, among other applications, without full tomography. However, it has been proven that for any physical process, the DME requires $\Theta(1/\varepsilon)$ state copies in error $\varepsilon$. In this work, we go beyond the lower bound and propose a procedure called the \textit{virtual} DME that achieves $\mathcal{O}(\log(1/\varepsilon))$ or $\mathcal{O}(1)$ state copies, by using non-physical processes. Using the virtual DME in place of its conventional counterpart realizes a general-purpose quantum algorithm for property estimation, that achieves \textit{exponential} circuit-depth reductions over existing protocols across tasks including quantum principal component analysis, quantum emulator, calculation of nonlinear functions such as entropy, and linear system solver with quantum precomputation. In such quantum algorithms, the non-physical process for virtual DME can be effectively simulated via simple classical post-processing while retaining a near-unity measurement overhead. We numerically verify this small constant overhead together with the exponential reduction of copy count in the quantum principal component analysis task. The number of state copies used in our algorithm essentially saturates the theoretical lower bound we proved.

Circuit knitting/cutting is a family of techniques that enables large quantum computations on limited-size quantum devices by decomposing a target circuit into smaller subcircuits. However, it typically incurs a measurement overhead exponential in the number of cut locations, and this scaling has long been believed to be fundamentally unavoidable. In this work, we show that such an exponential scaling is not universal: it can be circumvented for tree-structured quantum circuits via concatenated quantum tomography protocols. We first consider the task of estimating the expectation value of an observable within additive error $\epsilon$ for a tree-structured circuit with tree depth 1, maximum branching factor $R$, and bond dimension at most $d$ on each edge. Our approach uses quantum tomography to construct, for each cut edge, a local decomposition that eliminates the rescaling factors in conventional QPD, instead introducing a controllable bias set by the tomography sample size. As a result, we show that $\mathcal{O}(d^3R^3\ln(dR)/\epsilon^2)$ total measurements suffice, including tomography measurements. Next, we extend the tree-depth-1 case to general trees of depth $L\geq2$, and give an algorithm whose total measurement cost $\mathrm{poly}(d,K,1/\epsilon)$ scales polynomially with the number of cuts $K$ for complete multi-ary trees. Finally, we perform an information-theoretic analysis to show that, in a comparable tree-depth-1 setting, conventional circuit-cutting methods require at least $\Omega((d+1)^R/\epsilon^2)$ measurements. This exponential separation in the number of cuts suggests that the improvement is not solely due to the tree restriction, highlighting the essential role of tomography-based construction in reducing measurement overhead in hybrid quantum–classical computations.