Abstract A quantum algorithm is presented for efficiently computing partial sums and specific weighted partial sums of quantum state amplitudes. Computation of partial sums has important applications, including numerical integration, cumulative probability distributions, and probabilistic modeling. The proposed quantum algorithm uses a custom unitary construction to achieve the desired partial sums with gate complexity and circuit depth of , where represents the number of terms in the partial sum. For cases where is a power of two, the unitary construction is straightforward; however, for arbitrary , an efficient quantum algorithm is developed to create the required unitary matrix. Computational examples for evaluation of certain partial sums and numerical integration based on the proposed algorithm are provided. The algorithm is also extended to evaluate partial sums of even or odd components and more complex weighted sums over specified intervals.
Abstract A quantum algorithm is presented for efficiently computing partial sums and specific weighted partial sums of quantum state amplitudes. Computation of partial sums has important applications, including numerical integration, cumulative probability distributions, and probabilistic modeling. The proposed quantum algorithm uses a custom unitary construction to achieve the desired partial sums with gate complexity and circuit depth of , where represents the number of terms in the partial sum. For cases where is a power of two, the unitary construction is straightforward; however, for arbitrary , an efficient quantum algorithm is developed to create the required unitary matrix. Computational examples for evaluation of certain partial sums and numerical integration based on the proposed algorithm are provided. The algorithm is also extended to evaluate partial sums of even or odd components and more complex weighted sums over specified intervals.
We give quantum algorithms for estimating weighted exponential sums S(f,w,N)=∑k=0N−1wke2πif(k), with wk≥0, ∑kwk=1, and N=2n exponentially large. Under two explicit oracle assumptions -- efficiently computable prefix sums for the weights, enabling Grover--Rudolph state preparation, and a fixed-point circuit for f -- amplitude estimation yields S to additive error ε with O(ε−1log(1/γ)) oracle uses and polylog(N) gates per use; all bounds are full gate complexities, and the saving over classical sampling is quadratic in 1/ε. Applying this to the Riemann--Siegel formula, we prove that ζ(σ+it) in the critical strip can be estimated to accuracy δ with O(t(1−σ)/2δ−1) gates, hence O(t1/4δ−1) on the critical line, where O suppresses factors polylogarithmic in t/δ. At fixed accuracy this improves on the t1/2 Riemann--Siegel cost and on the best rigorous classical algorithm's t4/13+o(1); the quantum algorithm is advantageous precisely when δ≫t−3/52, which covers the accuracy needed to locate and count zeros. We show that a polylog(t) algorithm does not follow from these techniques -- undoing the normalization costs the ℓ1 mass ∑k≤Nk−σ=Θ(t(1−σ)/2) of the main sum -- and that Hiary-type block decompositions cannot improve the quantum query complexity. We also give an estimator for the magnitude of the amplitude sum ∣∑kak∣ of any efficiently preparable state, and review the required amplitude- and phase-estimation subroutines.
Abstract Wavelet transforms are widely used in various fields of science and engineering as a mathematical tool with features that reveal information ignored by the Fourier transform. Unlike the Fourier transform, which is unique, a wavelet transform is specified by a sequence of numbers associated with the type of wavelet used and an order parameter specifying the length of the sequence. While the quantum Fourier transform, a quantum analog of the classical Fourier transform, has been pivotal in quantum computing, prior works on quantum wavelet transforms (QWTs) were limited to the second and fourth order of a particular wavelet, the Daubechies wavelet. Here we develop a simple yet efficient quantum algorithm for executing any wavelet transform on a quantum computer. Our approach is to decompose the kernel matrix of a wavelet transform as a linear combination of unitaries (LCU) that are compilable by easy-to-implement modular quantum arithmetic operations and use the LCU technique to construct a probabilistic procedure to implement a QWT with a known success probability. We then use properties of wavelets to make this approach deterministic by a few executions of the amplitude amplification strategy. We extend our approach to a multilevel wavelet transform and a generalized version, the packet wavelet transform, establishing computational complexities in terms of three parameters: the wavelet order M , the dimension N of the transformation matrix, and the transformation level d . We show the cost is logarithmic in N , linear in d and superlinear in M . Moreover, we show the cost is independent of M for practical applications. Our proposed QWTs could be used in quantum computing algorithms in a similar manner to their well-established counterpart, the quantum Fourier transform.
Abstract We consider the problems of weighted constrained sampling and weighted model counting, where we are given a propositional formula and a weight for each world. The first problem consists of sampling worlds with a probability proportional to their weight given that the formula is satisfied. The latter is the problem of computing the sum of the weights of the models of the formula. Both have applications in many fields such as probabilistic reasoning, graphical models, statistical physics, statistics, and hardware verification. In this article, we propose quantum weighted constrained sampling (QWCS) and quantum weighted model counting (QWMC), two quantum algorithms for performing weighted constrained sampling and weighted model counting, respectively. Both are based on the quantum search/quantum model counting algorithms that are modified to take into account the weights. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWCS requires O(22n+1/WMC) O ( 2 n 2 + 1 / WMC ) oracle calls, where n is the number of Boolean variables and WMC WMC is the normalized between 0 and 1 weighted model count of the formula, while a classical algorithm has a complexity of Ω(1/WMC) Ω ( 1 / WMC ) . QWMC takes Θ(22n) Θ ( 2 n 2 ) oracle calss, while classically the best complexity is Θ(2n) Θ ( 2 n ) , thus achieving a quadratic speedup.
Quantum algorithms have shown their superiority in many application fields. However, a general quantum algorithm for numerical integration, an indispensable tool for processing sophisticated science and engineering issues, is still missing. Here, we first proposed a quantum integration algorithm suitable for any continuous functions that can be approximated by polynomials. More impressively, the algorithm achieves quantum encoding of any integrable functions through polynomial approximation, then constructs a quantum oracle to mark the number of points in the integration area and finally converts the statistical results into the phase angle in the amplitude of the superposition state. The quantum algorithm introduced in this work exhibits quadratic acceleration over the classical integration algorithms by reducing computational complexity from O(N) to O(√N). Our work addresses the crucial impediments for improving the generality of quantum integration algorithm, which provides a meaningful guidance for expanding the superiority of quantum computing.
It remains an open question whether the apparent additional power of quantum computation derives inherently from quantum mechanics, or merely from the flexibility obtained by "lifting" Boolean functions to linear operators and evaluating their composition cleverly. Holographic algorithms provide a useful avenue for exploring this question. We describe a new, simplified construction of holographic algorithms in terms of Pfaffian circuits. Novel proofs of some key results are provided, and we extend the approach of [34] to nonsymmetric, odd, and homogenized signatures, circuits, and various models of execution flow. This shows our approach is as powerful as the matchgate approach. Holographic algorithms provide in general O(nωp) time algorithms, where ωp is the order of Pfaffian evaluation in the ring of interest (with 1.19≤ωp≤3 depending on the ring) and n is the number of inclusions of variables into clauses. Our approach often requires just the evaluation of an n×n Pfaffian, and at most needs an additional two rows per gate, whereas the matchgate approach is quartic in the arity of the largest gate. We give examples (even before any change of basis) including efficient algorithms for certain lattice path problems and an O(nωp) algorithm for evaluation of Tutte polynomials of lattice path matroids. Finally we comment on some of the geometric considerations in analyzing Pfaffian circuits under arbitrary basis change. Connections are made to the sum-product algorithm, classical simulation of quantum computation, and SLOCC equivalent entangled states.
We present an efficient quantum algorithm for estimating Gauss sums over finite fields and finite rings. This is a natural problem as the description of a Gauss sum can be done without reference to a black box function. With a reduction from the discrete logarithm problem to Gauss sum estimation we also give evidence that this problem is hard for classical algorithms. The workings of the quantum algorithm rely on the interaction between the additive characters of the Fourier transform and the multiplicative characters of the Gauss sum.