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.
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.
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-enhanced (i.e., higher performance by quantum effects than any classical methods) mean value estimation of observables is a fundamental task in various quantum technologies; in particular, it is an essential subroutine in quantum computing algorithms. Notably, the quantum estimation theory identifies the ultimate precision of such an estimator, which is referred to as the quantum Cramér-Rao (QCR) lower bound or equivalently the inverse of the quantum Fisher information. Because the estimation precision directly determines the performance of those quantum technological systems, it is highly demanded to develop a generic and practically implementable estimation method that achieves the QCR bound. Under imperfect conditions, however, such an ultimate and implementable estimator for quantum mean values has not been developed. In this paper, we propose a quantum-enhanced mean value estimation method in a depolarizing noisy environment that asymptotically achieves the QCR bound in the limit of a large number of qubits. To approach the QCR bound in a practical setting, the method adaptively optimizes the amplitude amplification and a specific measurement that can be implemented without any knowledge of state preparation. We provide a rigorous analysis for the statistical properties of the proposed adaptive estimator such as consistency and asymptotic normality. Furthermore, several numerical simulations are provided to demonstrate the effectiveness of the method, particularly showing that the estimator needs only a modest number of measurements to almost saturate the QCR bound.
Quantum computing exists at the intersection of mathematics, physics, chemistry, and engineering; the main goal of quantum computing is the creation of devices and algorithms which use the properties of quantum mechanics to store, manipulate and measure information. There exist many families of algorithms, which, using non-classical logical operations, can outperform traditional, classical algorithms in terms of memory and processing requirements. In addition, quantum computing devices are fundamentally smaller than classical processors and memory elements; since the physical models governing their performance are applicable on all scales, as opposed to classical logic elements, whose underlying principles rely on the macroscopic nature of the device in question. \n \nQuantum algorithms, for the most part, are predicated on a theory of resources. It is often assumed that quantum computers can be placed in a precise fiducial state prior to computation, and that logical operations are perfect, inducing no error on the system which they affect. These assumptions greatly simplify algorithmic design, but are fundamentally unrealistic. In order to justify their use, it is necessary to develop a framework for using a large number of imperfect devices to simulate the action of a perfect device, with some acceptable probability of failure. This is the study of fault-tolerant quantum computing. In order to pursue this study effectively, it is necessary to understand the fundamental nature of generic quantum states and operations, as well as the means by which one can correct quantum errors. Additionally, it is important to attempt to minimize the use of computational resources in achieving error reduction and fault-tolerant computing. \n \nThis thesis is concerned with three projects related to the use of error-prone quantum systems to transmit and manipulate information. The first of these is concerned with the use of imperfectly-prepared states in error-correction routines. Using optimal quantum error correction, we are able to deduce a method of partially protecting encoded quantum information against preparation errors prior to encoding, using no additional qubits. The second of these projects details the search for entangled states which can be used to transmit classical information over quantum channels at a rate superior to classical states. The third of these projects concerns the transcoding of data from one quantum code into another using few ancillary resources. The descriptions of these projects are preceded by a brief introduction to representations of quantum states and channels, for completeness. \n \nThree techniques of general interest are presented in appendices. The first is an introduction to, and a minor advance in the development of optimal error correction codes. The second is a more efficient means of calculating the action of a quantum channel on a given state, given that the channel acts non-trivially only on a subsystem, rather than the entire system. Finally, we include documentation on a software package developed to aid the search for quantum transcoding operations.
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.
The detection and characterization of quantum coherence is of fundamental importance both in the foundations of quantum theory as well as for the rapidly developing field of quantum technologies, where coherence has been linked to quantum advantage. Typical approaches for detecting coherence employ {\it coherence witnesses} -- observable quantities whose expectation value can be used to certify the presence of coherence. By design, coherence witnesses are only able to detect coherence for some, but not all, possible states of a quantum system. In this work we construct protocols capable of detecting the presence of coherence in an {\it unknown} pure quantum state ∣ψ⟩. Having access to m copies of an unknown pure state ∣ψ⟩ we show that the sample complexity of any experimental procedure for detecting coherence with constant probability of success ≥2/3 is Θ(c(∣ψ⟩)−1), where c(∣ψ⟩) is the geometric measure of coherence of ∣ψ⟩. However, assuming access to the unitary Uψ which prepares the unknown state ∣ψ⟩, and its inverse Uψ†, we devise a coherence detecting protocol that employs amplitude-amplification {\it a la} Grover, and uses a quadratically smaller number O(c(∣ψ⟩)−1/2) of samples. Furthermore, by augmenting amplitude amplification with phase estimation we obtain an experimental estimation of upper bounds on the geometric measure of coherence within additive error ε with a sample complexity that scales as O(1/ε) as compared to the O(1/ε2) sample complexity of Monte Carlo estimation methods. The average number of samples needed in our amplitude estimation protocol provides a new operational interpretation for the geometric measure of coherence. Finally, we also derive bounds on the amount of noise our protocols are able to tolerate.
Quantum states and measurements are two central physical objects in the theory of quantum mechanics. The preparation, control and measurement of quantum states lies at the heart of modern quantum information processing protocols ranging from secure communication to quantum computation and precision sensing. And yet, the reliable operation of these advanced protocols ultimately rests on a far more essential prerequisite - our ability to calibrate, certify and benchmark the quantum states we prepare and the quantum measurements we perform. Quantum information theory provides a natural framework for these tasks, meaningfully connecting the resources we expend for characterisation with the accuracy and precision we can expect in return. While decades of advances in quantum information have refined our understanding of quantum characterisation and sharpened our practical ability to calibrate with enhanced precision, important questions about the fundamental limits of quantum characterisation remain unanswered. Although incorporating entanglement at the measurement stage is known to enhance the estimation of unknown quantum states, the extent of this improvement remains poorly understood. This leaves open a fundamental question on the utility of complex entangling measurement strategies, impeding progress towards bridging the significant gap between practically achievable precision and the ultimate theoretical quantum limit. Complementary to quantum state estimation, which is relatively well-established in theory and practice, the characterisation of quantum measurements lacks a rigorous information-theoretic foundation, leading to a dearth of principled benchmarks and provably optimal strategies despite growing experimental interest. This thesis develops and applies information-theoretic tools to answer questions in quantum characterisation, with an eye to enabling practical improvements beyond current techniques in the field. First, we introduce a computable measure of entanglement enhancement for quantum state estimation and study its variation across general multi-parameter estimation problems for higher-dimensional quantum states. We show that the entanglement enhancement is maximised for full qudit state tomography but grows only linearly with system dimension even when allowing an asymptotically large number of entangling operations. Our proposed tight upper bound to entanglement enhancement therefore constitutes a strong limitation on the utility of such entangling measurements. Next, we formulate the dual problem of quantum detector estimation, developing a comprehensive framework for maximally precise calibration centred around a newly introduced quantity - the detector quantum Fisher information. This information-theoretic measure stipulates the ultimate precision attainable for measurement calibration and identifies the optimal input states that achieve this precision. Further, our framework enables the first provably optimal detector estimation experiment and reveals the scope for entanglement-based enhancements, thereby placing measurement characterisation on equal footing with state characterisation. Considered together, these results suggest two contrasting conclusions about quantum characterisation. On the one hand, they show that for quantum state estimation, increasingly powerful entangling measurements offer only diminishing returns at the ultimate precision limit. On the other hand, they highlight practical quantum advantages available for detector estimation by providing a framework that can improve calibration performance and guide future experimental design. More broadly, these results complete and advance the triad of state, process, and detector characterisation, positioning quantum information measures as not merely abstract bounds, but practical guides for deciding when complex quantum resources are genuinely worth deploying and where near-term quantum advantages are most likely to be realised.