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 $|ψ\rangle$. Having access to $m$ copies of an unknown pure state $|ψ\rangle$ we show that the sample complexity of any experimental procedure for detecting coherence with constant probability of success $\ge 2/3$ is $Θ(c(|ψ\rangle)^{-1})$, where $c(|ψ\rangle)$ is the geometric measure of coherence of $|ψ\rangle$. However, assuming access to the unitary $U_ψ$ which prepares the unknown state $|ψ\rangle$, and its inverse $U_ψ^\dagger$, we devise a coherence detecting protocol that employs amplitude-amplification {\it a la} Grover, and uses a quadratically smaller number $O(c(|ψ\rangle)^{-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 $\varepsilon$ with a sample complexity that scales as $O(1/\varepsilon)$ as compared to the $O(1/\varepsilon^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.
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 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 phase estimation is a core task in quantum technologies ranging from metrology to quantum computing, where it appears as a key subroutine in various algorithms. Here, we quantitatively connect the performance of phase estimation protocols with quantum coherence. To achieve this, we construct and characterize resource theories of quantum networks that cannot generate coherence. Given multiple copies of a unitary encoding an unknown phase and access to a fixed coherent state, we estimate the phase using such networks. For a unified and general approach, we assess the quality of the estimate using a generic cost function that penalizes deviations from the true value. We determine the minimal average cost that can be achieved in this manner and explicitly derive optimal protocols. From this, we construct a family of coherence measures that directly connect a state's coherence with its value for phase estimation, demonstrating that every bit of coherence helps. This establishes coherence as a resource that quantifies the performance of phase estimation, and, thus, of any quantum technology relying on it as a subroutine.
Optimal single-copy estimation of quantum state moments: why Tr(ρ3) and Tr(ρ4) are equally hard
Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments Tr(ρt), allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity Θ(d) at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer t≥2: for any sufficiently small constant additive error, the optimal sample complexity is Θ(d1+⌈log2t⌉⌈log2t⌉) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h≥1, all moment orders 2h−1<t≤2h share the same exponent. In particular, the third and fourth moments both require Θ(d2/3) copies. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. We also establish an Ω(d1−1/t) lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every t≥4. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond d.
Consider a Boolean function χ:X→{0,1} that partitions set X between its good and bad elements, where x is good if χ(x)=1 and bad otherwise. Consider also a quantum algorithm A such that A∣0⟩=∑x∈Xαx∣x⟩ is a quantum superposition of the elements of X, and let a denote the probability that a good element is produced if A∣0⟩ is measured. If we repeat the process of running A, measuring the output, and using χ to check the validity of the result, we shall expect to repeat 1/a times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good x after an expected number of applications of A and its inverse which is proportional to 1/a, assuming algorithm A makes no measurements. This is a generalization of Grover's searching algorithm in which A was restricted to producing an equal superposition of all members of X and we had a promise that a single x existed such that χ(x)=1. Our algorithm works whether or not the value of a is known ahead of time. In case the value of a is known, we can find a good x after a number of applications of A and its inverse which is proportional to 1/a even in the worst case. We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform amplitude estimation, a process that allows to estimate the value of a. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of x∈X such that χ(x)=1. We obtain optimal quantum algorithms in a variety of settings.
Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given m Bernoulli distributions with unknown biases p1,…,pm and a gap parameter Δ, the goal is to estimate the fraction ρ of \emph{positive} distributions (pi≥1/2+Δ) to within additive error ε. We prove an upper bound of O~(Δερ+Δε1) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ2ε2).
Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of Ω(ρ/(Δε)) via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to O~(ερ+ε1) and Ω(ερ), thereby characterizing the query complexity of quantum counting with bounded-error oracles.
Quantum coherence has wide-ranging applications from quantum thermodynamics to quantum metrology, quantum channel discrimination, and even quantum biology. Thus, detecting and quantifying coherence are two fundamental problems in quantum resource theory. Here, we introduce feasible methods to detect and estimate the coherence by constructing coherence witnesses for any finite-dimensional states. Our coherence witnesses detect coherent states by testing whether the expectation value of the witness is negative or not. Two typical coherence witnesses are proposed and discussed based on our witness-constructing method, which are also used to estimate the robustness of coherence, the l1 norm, and the l2 norm of coherence measures. Furthermore, we compare one of our coherence witnesses with a previously introduced witness by proving that our witness is strictly stronger than that previous witness. We also present an application of coherence in a quantum metrology task, in which we estimate an unknown parameter by measuring our coherence witness.