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 Letter, 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 showing that, for a problem of estimating 2-body fermionic reduced density matrices, 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.
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 Letter, 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 showing that, for a problem of estimating 2-body fermionic reduced density matrices, 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.
In the accompanying paper of arXiv:2505.00697, we have presented a generalized scheme of adaptive quantum gradient estimation (QGE) algorithm, and further proposed two practical variants which not only achieve doubly quantum enhancement in query complexity regarding estimation precision and number of observables, but also enable minimal cost to estimate k-RDMs in fermionic systems among existing quantum algorithms. Here, we provide full descriptions on the algorithm, and provide theoretical guarantee for the estimation precision in terms of the root mean squared error. Furthermore, we analyze the performance of the quantum amplitude estimation algorithm, another variant of the Heisenberg-limited scaling algorithm, and show how the estimation error is minimized under the circuit structure that resembles the phase estimation algorithm. We finally describe the details for the numerical evaluation of the query complexity of the Heisenberg-limited algorithms and sampling-based methods to make a thorough comparison in the task of estimating fermionic k-RDMs.
Predicting local fermionic correlations is a central task in quantum many-body physics, as these correlations encode many physically relevant local observables. The ubiquitous particle-number symmetry imposes strong structural constraints on quantum states, suggesting that local correlations should be learned with fewer samples than by symmetry-agnostic approaches. However, it has remained unclear whether such a provable advantage exists in collective learning of local correlations. Here, we develop a framework of number-conserving fermionic-shadow tomography based on random orbital rotations. We prove that, for every given order k, we can simultaneously estimate all k-body fermionic correlations of an N-mode η-particle state with a given variance ε2 using only Ok(ηk/ε2) samples, which are independent of the system size N. We further establish a matching information-theoretic lower bound Ωk(ηk/ε2) for any adaptive protocol based on single-copy measurements, showing that the (ηk,ε)-dependence is optimal up to constants depending only on k. Furthermore, numerical studies show a 20-fold query reduction for one-body correlation estimation at N=200, η=20, and ε=10−2, compared with the best alternative including Heisenberg-limited estimation methods. Relative to fermionic Gaussian-unitary shadows, sample costs for the square-lattice Fermi-Hubbard model at N=288 are reduced by factors of 148 for energy density and 161 for spin structure factor estimation. For molecular energy derivatives with respect to atomic coordinates, our method reduces sample requirements by factors of 53 for Cr2 and 18.5 for [Fe2S2]2− at N=128. These results demonstrate the practical advantage of particle-number symmetry for fermionic observable estimation.
In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty that is quantified by variance or mean squared error of measurement outcome. While the uncertainty can be reduced by averaging several samples, the number of samples should be minimized when each sample is very costly. This is especially the case for fault-tolerant quantum computing that involves measurement of multiple observables of nontrivial states in large quantum systems that exceed the capabilities of classical computers. In this work, we provide an adaptive quantum algorithm for estimating the expectation values of M general observables within root mean squared error ε simultaneously, using O ( ε − 1 M log M ) queries to a state preparation oracle of a target state. This remarkably achieves the scaling of Heisenberg limit 1 / ε , a fundamental bound on the estimation precision in terms of mean squared error, together with the sublinear scaling of the number of observables M . The proposed method is an adaptive version of the quantum gradient-estimation algorithm and has a resource-efficient implementation due to its adaptiveness. Specifically, the space overhead in the proposed method is O ( M ) , which is independent from the estimation precision ε unlike noniterative algorithms. In addition, our method can avoid the numerical instability problem for constructing quantum circuits in a large-scale task (e.g., ε ≪ 1 in our case), which appears in the actual implementation of many algorithms relying on quantum signal processing techniques. Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
Quantum computers have great potential to uncover new and unexpected physical phenomena.They can simulate classically intractable many-particle quantum systems and probe them in a programmable, computational manner.They can also process experimental quantum data directly, enabling us to probe unseen aspects of physical systems that cannot be reached by any classical means.In both roles, refining quantum algorithms toward their fundamental limits expands and sharpens the reach of quantum computers.Among quantum algorithms, quantum estimation is of central importance because it elicits the physical properties of interest from quantum systems.Even in an ideal, noiseless setting, however, obtaining precise estimates of such properties is significantly resource-intensive, unless one leverages coherent quantum operations.While many quantum-enhanced (i.e., higher performance than any classical means enabled by quantum effects) estimation algorithms have been proposed under reasonable access assumptions, it is still an ongoing quest to design quantum algorithms achieving ultimate estimation efficiency allowed by quantum mechanics.In addition, rapid experimental progress makes us envision an early fault-tolerant regime with large-scale yet not fully error-corrected quantum computers.Toward this regime, it is also crucial to develop quantum estimation algorithms that elicit as much information of interest as possible from a quantum system subject to noise.In these contexts, this thesis advances quantum-enhanced algorithms for estimating physical properties in two respects: Heisenberg-limited multi-observable estimation and single-observable estimation for the early faulttolerant quantum computing (FTQC) regime.First, we provide an adaptive quantum algorithm for estimating expectation values of multiple observables simultaneously in an ideal (noiseless) setting.Given common access to block-encoded observables, a state-preparation unitary, and its inverse, this algorithm achieves a double quantum enhancement in query complexity to the state preparation and its inverse: the mean-squared-error (MSE) scaling at the Heisenberg limit and sublinear scaling in the number of observables.It also essentially matches the query lower bound in the small-additive-error regime (not in MSE), previously derived in quantum complexity theory.In addition, the proposed algorithm significantly reduces the number of ancilla qubits and the classical computation for circuit synthesis, compared to prior art for this task.The double enhancement and the circuit simplification come from a novel algorithm design that integrates key ideas from adaptive phase estimation, quantum amplification, and quantum gradient estimation.Next, we focus on expectation value estimation for a single observable in the early FTQC regime.In this regime, available coherent resources are mostly consumed for a state preparation unitary, and the dominant noise stems from that costly unitary and its inverse.Under a specific model reflecting these aspects, we derive the quantum-enhanced precision limit, that is, the minimal quantum Cramér-Rao bound over all possible estimation strategies in the model.Then, by designing an adaptive optimization based on Fisher information, we propose a quantum-enhanced estimation algorithm, with rigorous estimation guarantees, that asymptotically achieves the quantum Cramér-Rao bound, when the target system size is sufficiently large.Finally, we numerically demonstrate that the asymptotic behavior holds with only a few hundred measurements per step and a few tens of qubits.
Many quantum algorithms involve the evaluation of expectation values. Optimal strategies for estimating a single expectation value are known, requiring a number of state preparations that scales with the target error ϵ as O(1/ϵ). In this Letter, we address the task of estimating the expectation values of M different observables, each to within additive error ϵ, with the same 1/ϵ dependence. We describe an approach that leverages Gilyén et al.'s quantum gradient estimation algorithm to achieve O(sqrt[M]/ϵ) scaling up to logarithmic factors, regardless of the commutation properties of the M observables. We prove that this scaling is worst-case optimal in the high-precision regime if the state preparation is treated as a black box, even when the operators are mutually commuting. We highlight the flexibility of our approach by presenting several generalizations, including a strategy for accelerating the estimation of a collection of dynamic correlation functions.
We introduce a fast and accurate heuristic for adaptive tomography that addresses many of the limitations of prior methods.Previous approaches were either too computationally intensive or tailored to handle special cases such as single qubits or pure states.By contrast, our approach combines the efficiency of online optimization with generally applicable and well-motivated data-processing techniques.We numerically demonstrate these advantages in several scenarios including mixed states, higher-dimensional systems, and restricted measurements.Quantum information processing (QIP) promises advantages in a wide range of different contexts, including machine learning [2-4], chemistry simulation [5][6][7], and number theory [8,9].As such, the experimental effort to build useful QIP devices has exploded in recent years.In the course of this effort, quantum tomography is a valuable tool for diagnosing and debugging small quantum devices, and has subsequently seen a variety of different advances.In particular, Bayesian approaches to tomography which are especially well suited to utilizing prior information and adapting to changing experimental conditions have developed significantly in recent years [10-13], presenting a useful experimental tool [14][15][16].In this paper we demonstrate the efficiency and accuracy of an adaptive tomography protocol that we call PAQT: practical adaptive quantum tomography.PAQT intelligently selects new measurements based on the outcomes of previous ones [10,[17][18][19][20][21].Adaptivity has been experimentally demonstrated [14,15,[22][23][24][25], but is not currently standard practice.Though adaptivity increases accuracy, the computational costs incurred outweigh that of simply repeating standard measurements many times.The PAQT approach employs a simple heuristic that can be efficiently computed between measurements, even with embedded hardware [26][27][28][29].The algorithm we propose is therefore compatible with modern experimental design and avoids an important limitation of previous approaches.We base our algorithm off of self-guided quantum tomography (SGQT), which treats adaptive tomography as a direct optimization problem rather than a new optimization problem between each measurement [30].Though this affords an efficient and easy to implement adaptive heuristic, SGQT is not without its limitations.It requires assuming that the target state is pure, and it does not return rich region estimates for a state.What PAQT achieves is to effectively combine SGQT with conventional and easily-implemented tomographic estimators, such as the Bayesian particle filter or least-squares fit (LSF) estimators.Under this approach, an experimentalist can collect data using SGQT (even if its assumptions are not met), and then post-process this data using particle filtering or LSF.The benefit of PAQT is two-fold.(1) From the point of view of traditional tomography, it gives an adaptive tomography protocol requiring only modest computational resources, as the bulk of the computational cost is offloaded to post-processing.(2) From the point of view of simulation-based optimization tomography (such as SGQT), it effectively augments the output with region estimation providing a statistically robust quantification of uncertainty.Thus, while we do not explicitly demonstrate that the improved scaling of Ferrie [30] remains in the more general case considered here, PAQT does provide a practical and efficient procedure for performing adaptive quantum tomography with rigorous statistical principles.