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.
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.
In this thesis we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graph-property recognition. \n \nFor the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum algorithm for implementing unitary matrices that can be written as linear combinations of efficiently implementable unitary gates. This algorithm uses a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. \n \nIn the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set of size M, and our task is to identify x. We present the first quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program. \n \nWe then study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Our main result is an output-sensitive algorithm for Boolean matrix multiplication that multiplies two n x n Boolean matrices with query complexity O(n sqrt{l}), where l is the sparsity of the output matrix. The algorithm is based on a reduction to the graph collision problem and a new algorithm for graph collision. \n \nFinally, we study the quantum query complexity of minor-closed graph properties and show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.
A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N ≫ M , where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.
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 study the query complexity of quantum learning problems in which the oracles form a group G of unitary matrices. In the simplest case, one wishes to identify the oracle, and we find a description of the optimal success probability of a t -query quantum algorithm in terms of group characters. As an application, we show that Ω(n) queries are required to identify a random permutation in Sn . More generally, suppose H is a fixed subgroup of the group G of oracles, and given access to an oracle sampled uniformly from G , we want to learn which coset of H the oracle belongs to. We call this problem coset identification and it generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation. We provide character-theoretic formulas for the optimal success probability achieved by a t -query algorithm for this problem. One application involves the Heisenberg group and provides a family of problems depending on n which require n+1 queries classically and only 1 query quantumly.