The accuracies of modern quantum logic clocks have surpassed those of standard atomic fountain clocks. These clocks also provide a greater degree of control, because before and after clock queries, we are able to apply chosen unitary operations and measurements. Here, we take advantage of these choices and present a numerical technique designed to increase the accuracy of these clocks. We use a greedy approach, minimizing the phase variance of a noisy classical oscillator with respect to a perfect frequency standard after an interrogation step; we do not optimize over successive interrogations or the probe times. We consider arbitrary prior frequency knowledge and compare clocks with varying numbers of ions and queries interlaced with unitary control. Our technique is based on the semidefinite programming formulation of quantum query complexity, a method first developed in the context of deriving algorithmic lower bounds. The application of semidefinite programming to an inherently continuous problem like that considered here requires discretization; we derive bounds on the error introduced and show that it can be made suitably small.
The accuracies of modern quantum logic clocks have surpassed those of standard atomic fountain clocks. These clocks also provide a greater degree of control, because before and after clock queries, we are able to apply chosen unitary operations and measurements. Here, we take advantage of these choices and present a numerical technique designed to increase the accuracy of these clocks. We use a greedy approach, minimizing the phase variance of a noisy classical oscillator with respect to a perfect frequency standard after an interrogation step; we do not optimize over successive interrogations or the probe times. We consider arbitrary prior frequency knowledge and compare clocks with varying numbers of ions and queries interlaced with unitary control. Our technique is based on the semidefinite programming formulation of quantum query complexity, a method first developed in the context of deriving algorithmic lower bounds. The application of semidefinite programming to an inherently continuous problem like that considered here requires discretization; we derive bounds on the error introduced and show that it can be made suitably small.
We describe quantum interrogation schemes for passive atomic clocks. During any given interrogation period, the optimal interrogation algorithm depends on the state of the clock -- specifically on the frequency deviation of the flywheel (classical oscillator) from the atomic standard. As a clock runs, it is possible to estimate this deviation. Nonetheless, traditional schemes use the same, fixed algorithm for each interrogation period, which is necessarily independent of this prior knowledge. Here we present a dynamic scheme, tailoring our algorithms to the clock's state before each interrogation. These strategies are derived by constructing a complete model of a passive clock -- specifically, a probability distribution describing the estimated average offset frequency of the flywheel during both the upcoming interrogation period and interrogation periods in the past is updated via appropriate noise models and by measurements of the atomic standard.\nTo reduce the deviation from an ideal clock we optimize the next interrogation algorithm by means of a semidefinite program for atomic state preparation and measurement whose objective function depends on the updated state. This program is based on the semidefinite programming formulation of quantum query complexity, a method first developed in the context of deriving algorithmic lower bounds. The application of semidefinite programming to an inherently continuous problem like that considered here requires discretization; we derive bounds on the error introduced and show that it can be made suitably small.\nFinally, we implement a full simulation of a passive clock with power-law noise models and find significant improvements by applying our techniques.
We describe protocols for passive atomic clocks based on quantum interrogation of the atoms. Unlike previous techniques, our protocols are adaptive and take advantage of prior information about the clock's state. To reduce deviations from an ideal clock, each interrogation is optimized by means of a semidefinite program for atomic state preparation and measurement whose objective function depends on the prior information. Our knowledge of the clock's state is maintained according to a Bayesian model that accounts for noise and measurement results. We implement a full simulation of a running clock with power-law noise models and find significant improvements by applying our techniques.
Abstract Quantum query complexity is pivotal in the analysis of quantum algorithms, encompassing well-known examples like search and period-finding algorithms. These algorithms typically involve a sequence of unitary operations and oracle calls dependent on an input variable. In this study, we introduce a variational learning approach to explore quantum query complexity. Our method employs an efficient parameterization of the unitary operations and utilizes a loss function derived from the algorithm’s error probability. We apply this technique to various quantum query complexities, notably devising a new algorithm that resolves the 5-bit Hamming modulo problem with four queries, addressing an open question from Cornelissen et al (2021 arXiv: 2112.14682 ). This finding is corroborated by a semidefinite programming (SDP) approach. Our numerical method exhibits superior memory efficiency compared to SDP and can identify quantum query algorithms (QQAs) that require a smaller workspace register dimension, an aspect not optimized by SDP. These advancements present a significant step forward in the practical application and understanding of QQAs.
We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1) show that the workspace of a quantum computer can be limited to at most n+k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model; 2) give an algorithm that on input the truth table of a partial Boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries; 3) use semidefinite programming duality to formulate a dual SDP P/spl circ/(f, t, /spl epsi/) that is feasible if and only if f cannot be evaluated within error /spl epsi/ by a t-step quantum query algorithm. Using this SDP, we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations; 4) give an interpretation of a generalized form of branching in quantum computation.
We consider the problem of designing an optimal quantum detector to minimize the probability of a detection error when distinguishing among a collection of quantum states, represented by a set of density operators. We show that the design of the optimal detector can be formulated as a semidefinite programming problem. Based on this formulation, we derive a set of necessary and sufficient conditions for an optimal quantum measurement. We then show that the optimal measurement can be found by solving a standard (convex) semidefinite program. By exploiting the many well-known algorithms for solving semidefinite programs, which are guaranteed to converge to the global optimum, the optimal measurement can be computed very efficiently in polynomial time within any desired accuracy. Using the semidefinite programming formulation, we also show that the rank of each optimal measurement operator is no larger than the rank of the corresponding density operator. In particular, if the quantum state ensemble is a pure-state ensemble consisting of (not necessarily independent) rank-one density operators, then we show that the optimal measurement is a pure-state measurement consisting of rank-one measurement operators.
We give semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, we consider SDP instances with m constraint matrices of dimension n, each of rank at most r, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then we show there is a quantum algorithm that solves the SDP feasibility problem with accuracy ϵ by using mlogm⋅poly(logn,r,ϵ−1) quantum gates. The dependence on n provides an exponential improvement over the work of Brand\~ao and Svore and the work of van Apeldoorn et al., and demonstrates an exponential quantum speed-up when m and r are small.
We apply the SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state ρ, we show we can find in time mlogm⋅poly(logn,r,ϵ−1) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ on the m measurements up to error ϵ. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle.
As in previous work, we obtain our algorithm by quantizing classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension based on the techniques developed in quantum principal component analysis, which could be of independent interest.