Provable Quantum Algorithm Advantage for Gaussian Process Quadrature
Authors: Cristian A. Galvis-Florez
Ahmad Farooq
Simo Särkkä
Venue: Accepted by TMLR ()

Abstract: The aim of this paper is to develop novel quantum algorithms for Gaussian process quadrature methods. Gaussian process quadratures are numerical integration methods where Gaussian processes are used as functional priors for the integrands to capture the uncertainty arising from the sparse function evaluations. Quantum computers have emerged as potential replacements for classical computers, offering exponential reductions in the computational complexity of machine learning tasks. In this paper, we combine Gaussian process quadrature and quantum computing by proposing a quantum low-rank Gaussian process quadrature method based on a Hilbert space approximation of the Gaussian process kernel and enhancing the quadrature using a quantum circuit. The method combines the quantum phase estimation algorithm with the quantum principal component analysis technique to extract information up to a desired rank. Then, Hadamard and SWAP tests are implemented to find the expected value and variance that determines the quadrature. We use numerical simulations of a quantum computer to demonstrate the effectiveness of the method. Furthermore, we provide a theoretical complexity analysis that shows a polynomial advantage over classical Gaussian process quadrature methods.  The code is available at https://github.com/cagalvisf/Quantum_HSGPQ.

Published in Transactions on Machine Learning Research (02/2025)
Provable Quantum Algorithm Advantage for Gaussian Pro- cess Quadrature
Cristian A. Galvis-Florez
cestiin.ggllis@oallle
Deportment of Electrical Engineering and Automation Aolto Universily, Finland
Ahmad Farooq
fammaddarroo@oaatt...
Department Electrical Engineering and Automation Aolto University, Finland
Simo Särkkä
simo.sarkkauualto.
Department of Electrical Engineering and Automation Aolto University, Finland
Reviewed on OpenReview: https: // openreview. net/ forum? K6CUWPLF62
Abstract
The aim of this paper is to develop novel quantum algorithms for Gaussian process quadra- ture methods. Gaussian process quadratures are numerical integration methods where Gaus- sian processes are used as functional priors for the integrands to capture the uncertainty arising from the sparse function evaluations. Quantum computers have emerged as poten- tial replacements for classical computers, offering exponential reductions in the computa- tional complexity of machine learning tasks. In this paper, combine Gaussian process quadralures and quantum computing by proposing a quanlum low-rank Gaussian process quadrature method based on Hilbert space approximation of the Gaussian process kernel and enhancing the quadrature using & quantum circuit. The method combines the quan- tum phase estimation algorithm with the quantum principal component analysis technique to extract information up to a desired rank. Then, Hadamard and SWAP tests are im- plemented to find the expected value and variance that determines the quadrature. We numerical simulations of quantun computer to demonstrate the effectiveness of the provide theoretical complexity analysis that shows polyno-
method. Furthermore, mial advantage over classical Gaussian process quadrature methods. The code is available at https:/// gi thub. cwm/ conn/aaaaliiss/uuntuuu HSCPQ.

---

Published in Transactions on Machine Learning Research (02/2025)
1
Notation
Classical notation
P
Random variable has distribution P
D
Data set D {(x,, vi) i ,,,., Expectation of fxx at x. given the data set D Kernel function evaluated at x and x'
E[f(x.) [D]
x(x,x')
K or K(X,X)
N X N covariance (or Gram) matrix Gaussian distribution over æ with mean l and covariance
M(x n. E)
vI((x.) D
Variance of [xx x x, given the data set D Transpose of the vector
x
8.g
Kroneeker delta, 6ig = 1 iff i jj and otherwise Eigenvalue of an eigenfunction or singular value a matrix Standard deviation of noise or a scale parameter
(x(x)
The ith eigenfunction of the Laplace operator
Quantum computing notation
2
Tensor product
1-)
Ket notation of column vector
61
Bra notation for the conjugate transpose of |+)
(1)
Braket or inner product between two vectors
Tensor product of the two separate ket vectors
1) (1
Outer product between two vectors Orthonormal basis state of integer j Tensor product of quantum systems
(2)
Lii) 60 liz) =
lzi) l5z) lirj2)
(5)
Used for intermediate states in the quantum algorithms Expected value of U over the quantum state (vb
(bbl U (16) (U))
(xx)
Quantum state encoding the data matrix X
Im (.)
Imaginary part the value Probability to measure the quantum system in the state (X)
Ps
Re (-)
Real part of the value
tr, (-)
Partial trace over nih subsystem
U
Unitary quantum operator. Matrix with components Us = (i)
Density matrix
p
Density matrix
p(n)
Density matrix of nth subsystem
2

---

Published in Transactions on Machine Learning Research (02/2025)
2 Introduction
The integration of analytically intractable functions is usually addressed by numerical methods such as clas- sical quadrature rules (Davis & Rabinowitz, 1984). However, alternatives to the classical quadrature rules are Bayesian quadratures which formulate the numerical integration problem as Bayesian inference prob- lem over the integral value, hence allowing for quantification of uncertainty arising from the finite mumber of function ovaluations (O'Hagan, 1991; Minka, 2000; Hennig et al., 2022). In particular, a common way is to consider a Gaussian prior distribution for the integrand, which leads to so-called Gaussian process quadra- tures (GPQs) (Minka, 2000; Hennig et al., 2022). However, the GPQ methods struggle with computational efficiency, especially when handling large datasets since the algorithm complexity scales as O(N"), with N being the number of evaluation points, which is problem inherited from the similar complexity challenge in Gaussian process regression.
Quantum computers have emerged as a novel approach for general computational purposes, showing even exponential speedups in computational complexity over their classical counterparts. Quantum computers exploit superposition, entanglement, and interference to perform a task, which substantially reduces the computational complexity of an algorithm (Niclsen & Chuang, 2011). The Harrow-Hassidim-LLloy algorithm (Harrow et al., 2009), quantum kernel methods (Schuld & Killoran, 2019), quantum phase estima- tion (QPE, Kitaev, 1995), and quantum amplitude amplification (QAA, Brassard et al., 2002) are quantum algorithms that offer a computational advantage in different numerical tasks (Schuld et al., 2016; Shor, 1994; Grover, 1996; Wiedemann et al., 2023; Canatar et al., 2023). Quantum algorithms for numerical integra- tion in the classical setting have been proposed by Yu et al. (2020) and Shu et al. (2024). Furthermore, Carrera Vazquez & Woerner (2021) and Martínez de Lejarza et al. (2023) implement quantum algorithms that have a quadratic spoedup with respect to Monte Carlo integration methods. These integration methods for classical numerical integration on a quantum computer have been proposed as an application of efficient. state preparation for quantum amplitude estimation (Martinez de Lejarza et al., 2023).
(HHL)
The contribution of this paper is to propose a quantum Bayesian quadrature algorithm for numerical inte- gration. A naive numerical integration algorithm using a Gaussian quadrature on a non-quantum classical computer would have a complexity of O(N)), which is inherited from the complexity of Gaussian process re- gression (Rasmussen et al., 2006). In this paper, we develop a low-rank quantum Gaussian process quadrature method for numerical integration employing low-rank Gaussian process prior, using the GPR method in Farooq et al. (2024) the starting point. Our algorithm harnesses the quantum Fourier transform, quantum phase estimation, and quantum principal component analysis to exploit the superposition of quantum states for computing the matrix inverse in GPQ, thereby providing an advantage over the classical approach. The proposed method begins by implementing a Hilbert space kernel approximation (Solin & Särkkä, 2020) using a classical computer to evaluate the basis function integrals at the evaluation points. Then, the resulting data matrix needs to be loaded into a quantum computer efficiently, and for this purpose, the approximate quan- tum amplitude encoding scheme implemented (Nakaji et al., 2022). Using quantum principal component analysis (qPCA) (Lloyd et al., 2014) and QPE we extract information about the dominant eigenvalues of the previously encoded data matrix. This information is used to implement conditional rotations that allow the ion of the expected value and the variance of the quadrature using Hadamard and SWAP test respectively (Schuld& & Petruccione, 2021; Buhrman et al., 2001). We provide the numerical simulation of our proposed solution for quantum low-rank Gaussian process quadrature in a classical processor that simulates a quantum computer, allowing us to compare it with classical Gaussian process quadrature methods.
Our method also provides polynomial computational advantage compared to classical methods for Gaussian process quadrature. The quantum algorithm implemented in this paper delivers complexity O(log(M) ) s2 /e), where is the condition number, is the sparsity of the matrix, is the desired level of accuracy, and M is the number of basis functions used in the Hilbert space approximation (usually M & N), with given quantum data, and O(poly plooyy(oo(())) N M)) (og(M)x"=>>) when data is given classically. The compu- fational complexity of a GPQ method implemented on a classical computer with the Hilbert space met would be (M and hence, the advantage is polynomial.
The paper is organized as follows. In Section 3 we briefly review the Gaussian process quadrature methods and show how to approximate them with the Hilbert space method. In Section 4 we summarize the generic
3

---

Published in Transactions on Machine Learning Research (02/2025)
quantum algorithms used in this paper. Section 5 encompasses the core of this work, presenting the quantum low-rank Gaussian process quadrature method and discussing its computational complexity. In Section 6 numerical simulations using a classical computer are shown. Section 7 concludes the work.
3 Hilbert Space Approximation for Gaussian Process Quadrature
Gaussian processes f ~ GP (0, (x,x')) can be used as functional prior distributions to model unknown functions f over a d-dimensional inputs x on to a space Ω C Rd. The covariance function k (x, x') defines the properties of the unknown function f and the mean can often be assumed to be zero, as we do here. Regression of a function f(x) can be performed using the Gaussian process as the prior distribution in a al., 2006). Then, set of N noisy measurements D {X' (x,,..,, x (y),'.. ,UN)) with yi fxx)) + ei, where e, N (0, on new point induce a posterior Gaussian distribution p (f(x.) x. D) N (f(x.) ( [f(x)))
process known Gaussian process regression (GPR) (Rasmussen
x, given by
Exf(x,) D] k. (K 021) -1 y, (f(x)) P] xx., k, (K + oK+o -0) k.
(1)
(2)
Here, K is N x N matrix with entries Kij xxx; and k. vector with the ith entry being (xx,, x:).
The choice of the covariance or kernel function defines the properties of the Gaussian process regression solution. A common kernel choice for GPR is the squared exponential covariance function (Rasmusscn et al., 2006)
(- x'112
k xx,x')== of ox
(3)
where o and are the signal scale and length scale hyprpaarameters respectively. Gaussian processes can also be used to construet Bayesian quadrature rules leading to so-called Gaussian process quadratures (Minka, 2000; Hennig et al., 2022) which we discuss next.
The objective of a Gaussian process quadrature is to estimate the integral of given function f(x) over a domain S against weight function p(x), that is,
I / (x))xxx)dxx
(4)
To perform this estimation, we consider a Gaussian process approximation of the function / conditional on a finite set of evaluation points y with y/ = f(x)) + 6, at some given evaluation points x,. Then the conditional expected value of the integral given this data D is
i
E[f(x) (x))dx
(5)
J x(Xxx))(x)dx (K (2+021)
which can be used as an estimator for the integral ~ I. Similarly, we can evaluate the variance of the estimator. The resulting conditional expected value and variance are given by (Hennig et al., 2022; Karvonen & Särkkä, 2017)
QBQ kx)x)T (K + -2) y, VBQ = y (kw) - (x) TK + -1)-1kk(()))
(6)
(7)
where the i-th component of the vector (2)) (x;) Sn k(x,, (x)xxx and the scalar μ (k,.) Sa Sg k(x, x'))(x)dxx((x)dd) The resulting quadrature QBQ approxinates the integral I by performing integration over the kernel rather than the function f itself, and by using these values it forms weights for
4

---

Published in Transactions on Machine Learning Research (02/2025)
the function values. There exist number of methods that can be used to reduce the complexity of Gaussian process regression such as inducing point methods Caiinoneo-CCanella & Rasmussen, 2005) and Hilbert space kernel approximations (Solin & Särkkä, 2020), which can be used to speed up the GPQ rule.
In this paper, we implement the Hilbert space method of Solin & Särkkä (2020) on the quadrature rule to reduce the complexity of the operation. We start by considering the eigenvalue problem of the Taplace operator in a well-behaved domain Ç such that the eigenfunctions and eigenvalues of the operator exist. The solution would give set of cigenfunctions (x(x) with correspondent real and positive eigenvalues X (Arfken et al., 2005). The eigenfunction are orthonormal respect to the inner product J @o dig. defining Hilbert space over Ç.
If the kernel function is isotropic, that is, l(x, x') = k[[[x - x'I),, then the covariance function can be approximated in the domain ( as (Solin & Särkkä, 2020)
M
k xxxx''
s
(vAs) (x(x) (x',
(8)
j=1
where the spectral density S(w) is the Fourier transform (F) of the scalar covariance function k(r) - S(w) where J = ||x x'||-
Equations (6) and (7) can be written in terms of the approximated kernel, giving
QBQ
~ [ T +
- ---==-)--075 y,
(9)
VBQ
4 Φ 02 -) 1)11d)
3yp:
(10)
where the vector B has the components TRu = (1)x(( A is a diagonal matrix with components
Ajj (())) and the matrix & has components b. = (x:). The approximation of the kernel now depends on the domain Ç. which is not necessarily the same as the integration domain Ω. The matrix in
Eqs. (9) and (10) that needs to be inverted now has rank M instead of N. This kernel approximation reduces the computational complexity involved in matrix inversion provided that M N.
The expected value and variance expressions of the quadrature can be decomposed using singular value decomposition (SVD) to embed them into quantum states (Schuld al., 2016). Some modifications of Eqs. (9) and (10) must be done before the implementation of the algorithm (Farooq et al., 2024). For the GPQ, we need to obtain the eigenvalues and eigenvectors of (TT 4b + - which we aim to express in terms of & d. By writing the expected value and variance of the quadrature in terms of this common set of cigenvectors, the expected value and variance can be written in terms of quantum states.
Similarly to Farooq et al. (2024) we start by considering X = AVA E NxM, where VA is a diagonal matrix with elements VAn = S(()), the quadrature equations take the form
QBQ X X
x
+ o - X
(11)
VBQ
oax [X X
+ o - X
(12)
where X = $I A.. Now the eigenvectors of X T X II are the same as those of X X. Previous equations are referred to as the Hilbert space quadrature (HSQ). In this paper, we use a quantum computer to calculate these quantities, which we call the quantum Hilbert space quadrature method (QHSQ). The variables X and X2, are computed a classical computer before we feed them into the quantum computer.
Using singular value decomposition (SVD) to the data matrix X it is possible to write the expected value and variance of the GPQ in terms of quantum states. Let X = UΣVT be the SVD of the data matrix X. The matrix Σ e R R is diagonal, containing the real singular values ,g, AR. being R the rank of the matrix X. The orthogonal matrices U E R and V E RRXM correspond to the left and right singular vectors, respectively. Thereof, the SVD of X x I'I VE'VT leads to the diagonal matrix Σ' with elements Σ/ = X² +02. Then, the eigendecomposition of (x x + TT) T is given by
n
x x 'x
U Σ
=
v
(13)
X2 + o2
5

---

Published in Transactions on Machine Learning Research (02/2025)
where Σ" is diagonal with components Σx A x and the vectors u, and v, correspond to the r-th column vectors of the matrices U and V respectively. Then, using the SVD, the expected value and varianco of the GPQ can be writlen as
A
QBQ
Σ
X
V,
(14)
+
+
0²
VBQ
a²
Σ 1 + V.V.
(15)
The SVD in the expected value and variance of the GPQ allows us to write them as expected values of quantum operators, extending the complexity reduction provided by the Hilbert space approximation of the kernel into the quantum algorithm.
4 Quantum Algorithm Background
In this section, we will review the quantum algorithms needed to implement the quantum low-rank Gaussian process quadrature. Roaders who are familiar with fundamental quantum algorithms can skip this section and directly move to the next Section 5. We have provided more details on the representation of quantum states, unitary transformation operations, and quantum measurements in Appendices A.1, A.2, and A.3.
4.1 Quantum Fourier transform
The quantum Fourier transform (QFT) performs the same transformation the discrete Fourier transform. It was first used in Shor's integer factoring algorithm (Shor, 1994). Nowadays, QFT is essential part of various quantum linear algebra algorithms such quantum phase estimation, matrix inversion problems, and qPCA (Nielsen & Chuang, 2011; Harrow et al., 2009; Lloyd et al., 2014). The discrete Fourier transform takes an input vector x and transforms it into another vector in the frequency domain through
2
5k
Ij:
k == 0..... 2"
(16)
2
1=
Similarly, QFT is defined as a linear operator that acts on an orthonormal basis [0),..., , IN 1) where N = 2", The QFT acts over the basis element Ij) as
1
[k).
(17)
2
k=0
We express this the unitary transformation
2
2
Smigk
U
(b) (1l.
(18)
k=
acting on arbitrary state (b)), which can be expressed
2"
(6b
Σ my
Σ yh lk)
(19)
To understand how the QFT has been implemented quantum computers, it is helpful to express the state ()) in binary representation as j "-jr- where f1.J2, .hn either 0 or 1. For example,
represent the state Ij) when j 2 as unit vector using binary representation: (2) [10) = [1] Φ [0)
0)T, where single qubit states are (0) = ( and [1) = (i) The binary representation of an
O0 0

---

Published in Transactions on Machine Learning Research (02/2025)
entire number can be written as j = j12n-1 -122 + 2n. Similarly, decimal number 0.j1 -
can be expressed in binary representation as j1/2 52/4 / +. j1/2'. The QFT in Eq. (17) can be written in product form following Nielsen & Chuang (2011) as
1 JI (n) 2n/2 [(10) 2mm00.5 [1)) (10) + 22mi0.jn-2h 12n [1)) (10) + 2 [1))]
(20)
This expression can be implemented using a quantum circuit composed only of the Hadamard gate H = and the two-qubit controlled rolation CR2 Rx
1
given in block-diagonal form, where
v2
1
-1]
Rs
The action of the Hadamard gale on the target quantum state (it) is
221/22
H (i) = V2 (10) +e 23 - (1)) /2 (10) + e 2 (1)).
(21)
where we represented the je/2 as a decimal number 0.jr- The Eq. (21) can be seen as follows: when je = 0, 1
we have H (0) v (10) + [))), and when je = we have H 1) = v2 (10) -1))- On the other hand, the two-qubit state (jajt), where the first qubit is the control and the second is the target,
operation of CR2 does not affect the second qubit if the first is in the zero state CR& (0j.) = (0jt), and when the control qubit in one state is CR [1jx) = e 3 (1j)).
We start with an n-qubit input quantum state representod l ... -n). Applying the Hadamard gate the first qubit gives the following quantum state
1 (0) + e مياية (1)) 152 112-.-j))...)
H (i) 112 ... 1n) = 21/2
21/2 (10) + 2m00,51 (1)) 1i2. -ja))
(22)
Then, the operation of the controlled-RR R2 gate to the first two qubits results in
CR2 (i1z2) lis..... (aa..-nn)) (n) 21/2 (0) + e (1)) 1.2.... jn) 21/2 (10) + 2md0-iiia [1)) .. (-))--)))..... (23)
1
1
Similarly, applying the controlled gates Rs for = 3,...,n on the first qubit yields the following expression:
1 (G)) 21/2 (10) - 2xth 1250:///22////ttt (1)) 1ó2 ... ..)) 21/2
-
1 (10) + 2n (1)) Liz 1.2-.-5h. .n)) (24)
where (&t) an intermediate quantum state. We then apply the Hadamard gate to the second qubit and repeat. the controlled operation of Rs for k 3,...,M n on the second qubit giving
E = 22/2 (10) + 5. (1)) (10) + 22t0- (1)) Lia ..))
(25)
We contimue in this fashion for each qubit until k = and perform the SWAP operation to change the location of the least significant bit, which leads us to the final quantum state
(Ea) (1)) + 22x00.in (1)) (10) + 20 11)) ... (10) + 22000 (1))
(26)
2n/2
Fig. 1 shows the circuit demonstration of the QFT. In the first step, Hadamard gate and n-1 conditional rotation gates make total of n gates. Similarly, in the second step, require = n(n + 1)/2. Therefore, the computational complexity of the QFT is O(n²). In contrast, representing the same amount of information on a classical computer requires N = 2n classical bits. Therefore, implementing the discrete Fourier transform using the classical fast Fourier transform (FFT) would require computational complexity of Onn")). The QFT is often used as a subroutine of several quantum algorithms such as quantum phase estimation, which we discuss in the next section.
gates. Continuing in
this manner, the total number of gates is n + (n - 1) +.. ........... +
7

---

Published in Transactions on Machine Learning Research (02/2025)
(1>
(Ea
(d1)
R2
R
(d2)
Ra-2
R
{3)
1i--1 1)
H
R₂
(jn)
Figure
Circuit diagram implement the quantum Fourier transform on a quantum computer.
4.2 Quantum phase estimation
Given unitary operator U acting qubit quantum state (ø) with eigenvalue equation U (o) 2mip (Ø), the objective of the quantum phase estimation (QPE) algorithm is to estimate the value of yp (Kitaev, 1995). The QPE starts with unitary transformation that can implement powers of U conditioned on ancillary qubits
1))
k)) 1))*
(27)
2n/2
2n/2
The action of the unitary operator U the eigenvector (ø) yiclds the eigenvalue e given
2
1K)
U (0)
(k) (e 2miko ((b)
2
2n/2
k=
k=0
2"
2mikip (k) lo)
2n/2
k=0
Applying the inverse QFT to the equation above results in the eigenvalue estimate being stored in the quantum register as follows
2riko [k) (0)
QFT!
(p) (Ø).
(28)
2n/2
Quantum registers consist of multiple qubits that are used in quantum computers, similar to classical registers in classical computers (Nielsen & Chuang, 2011). We then perform a measurement the computations ional basis to obtain the estimate & of the eigenvalue.
The binary string I with the highest success probability corresponds to the exact estimate & only if & 2n Generally, & cannot be represented exactly by gu however, the QPE algorithm still gives the best possible approximation, according to Kitaev (1995), given by
2
2mikop kk) (0)
QFT
2nih(t- j/2"")
(i) (o)
(29)
2n/2
2n/2
A=
k=0
The highest success probability of measuring the closest estimate using the QPE algorithm becomes
2
p()) =
2atk(o-j/2")
(30)
2n/2
k=
8

---

Published in Transactions on Machine Learning Research (02/2025)
(0)
QFT
())
U
Figure 2: Circuit diagram to implement the quantum phase cstimation quantum computer.
This depends on the difference between and the binary fractional integer j/2". Therefore, to increase the precision of the estimate Φ, we need to add more ancilla qubits to the QFT. Fig. 2 presents the circuit of the quantum phase estimation algorithm.
QPE requires the implementation of powers of the unitary operator ef on quantum computer using Hamiltonian simulation of the H operator (Lloyd, 1996). Standard methods implement Hamiltonian simulation involve decomposing the unitary matrix into all possible combinations of Pauli operators which has a huge computational complexity (Niclsen & Chuang, 2011). To obtaín practical advantages over classical systems, we have to find solutions in which we can efficiently simulate the unitary system. Several algorithums have been proposed in this area, for example, Berry et al. (2007) consider a sparse Hamiltonian operator, another approach approximates using Taylor series (Berry et al., 2015), and the commonly used Suzuki- Trotter method (Suzuki, 1976). Hamiltonian simulation can be efficiently done when the input state and the Hamiltonian operator are the same (Tloyd et al., 2014), with method called density matrix exponentiation. It can be used in the quantum principal component analysis (qPCA) if the quantum density operator is non-sparse but low-rank. In this paper, utilize this concept of qPCA for the Gaussian process quadrature rule.
4.3 Quantum principal component analysis
Instead of explicitly calculating the unitary matrix U = eBBt we can simulate the unitary operation using SWAP operators. For this, we add the extra condition that the Hermitian operator should be represented as the density matrix of some quantum stale, that is, A = p. We apply the SWAP operation to the state أ 8 ē and perform a partial trace operation. The expression for this simulation turns out to be (Lloyd et al., 2014; Schuld & Petruccione, 2021)
trfe -15Ar 18At (ā e (SA)] = 5- iAll 5| +(A())
Re - 1PA1
where ā - iAt(ā ō] with [ā,ā] pō op the first terms of Taylor expansion of Ge and trz(-) is partial trace over second subsystem.
Density matrix exponentiation is often used with the quantum phase estimation technique. Once we have exponentiated the density matrix, we can extract the eigenvalues through quantum phase estimation. To do so, we need to prepare the powers of U clokat
Lloyd al. (2014) showed that using the exponential density matrix along with the estimation of the quantum phase, O(E-3) copies of ğ are required for this, where represents the precision estimate the eigenvalues. These copies then combined with ancilla register of qubits in superposition to obtain
2" Pes
Σ K=0
bb) ( (()) & 2 0 ... 8 2")
(31)
9

---

Published in Transactions on Machine Learning Research (02/2025)
We now perform sequence of two-qubit conditional SWAP operators, each of which swaps the first qubit state o with the gth copy of conditioned on the ancilla qubit [k). The SWAP operators are entangled with the ancillary register, so the index [k) governs the sequence of SWAP operators up to the copy p(k) as
1 Ps.
Ikat) (kAt & II
e
(32)
K
k=
After taking the partial trace over all the copies of p, we obtain the result
PSc
1k) (k) 8 oe ihpAr + +(A(2))
(33)
K=0
This mixed quantum state representation is suitable for applying the QFT (Schuld & Petruccione, 2021). Letting ē A, it calculates the eigenvalues and cigenvectors of the operator p. Obtaining cigenvalues and eigenvectors in this way is known as quantum principal component analysis.
The SWAP operator a sparse matrix and can be simulated efficiently. Lloyd et al. (2014) showed that this algorithm can be implemented with a computational complexity of Ollog N) on a quantum computer when multiple copies of the density operator are already given as quantum states. This qPCA is qubit efficient as long we do not have to estimate the eigenvalue to precision that does not grow exponentially. According to Lloyd et al. (2014), this technique is only suitable when the density matrix is dominated by few eigenvalues that do not require high precision for estimation.
5 Quantum Hilbert space low-rank Gaussian process quadrature
In this section, provide the main contribution of our paper, which explores how quantum computers can be used to evaluate integrals using the Hilbert space low-rank Gaussian process quadrature. For this, we implement the Hilbert space kernel approximation developed by Farooq et al. (2024) for quantum-assisted Gaussian process regression and extend it to the GPQ rule. We start with the data matrix X E NNM computed on a classical computer. This data matrix is exactly the same as used Eqs. (11) and (12). We initially consider the amplitude encoding scheme in Appendix A.4 to encode the data matrix X with entries 2y in the form
M-IN-1 (xx) ΣΣ
"x (m) /n)
(34)
The state |/x) has to be normalized, then, the entries x/ satisfy the condition Σn,m || 1. The ampli- tude data encoding implicates a computational complexity O(NM) in standard quantum state preparation methods (Schuld & Petruccione, 2021). However, efficient quantum amplitude encoding methods have been recently proposed, achieving a (ipoly(log(MM)) computational complexity (Nakaji et al., 2022).
Starting from the quantum state in Eq. (34), we consider its Gram-Schmidt decomposition (Schuld et al., 2016) which gives
(xx)
Σ
Ar (2,) (ur)
(35)
The Gram-Schmich decomposition works quantum analog of the SVD performed in (14). Further, consider the density matrix PxTx Tr, (lex) (/xl} given by tracing out the In) register of the quantum state in Eq. (34). The resulting density matrix can be written in terms of the Gram-Schmidt decompasition in Eq. (35) as
R PxTx = Tr, Tr,((/xx))))))) (bxl) = Σ
x2 (u)) (vr)-
(36)
Once the density operator is built, is possible to apply it an exponential evolution operator to the [m) register of (xx) following the qPCA technique (Lloyd al., 2014) explained in Section 4.3. Since the state
10

---

Published in Transactions on Machine Learning Research (02/2025)
(2))
10%
(01)
10)+
H
QFT
QFT
H
(M)
exxx
[(xx
(o))(N)
QPE
Figure 3: Quantum circuit to prepare the (&) quantum state. The red gales represent the parts of the algorithm where the qPCA is implemented, meanwhile, the green part envelopes the implementation of the QPE algorithm.
(x) is the cigenstate of the operator in Eq. (36), it is also the eigenstate of cxp(-ipxTxt). With this argument, is possible to implement the QPE algorithm (see Section 4.2) to estimate the eigenvalues of P.TX.
The algorithm starts by building specific state [τ)) that stores the information of the evaluation points. Fig. 3 shows the quantum circuit used to create this state. Four quantum registers are needed, the last two are the In), and [m),, registers needed to store (xx); then, we need a register 10), that will store the eigenstates; finally, we need an ancilla register (0),. From Fig. 3, we can see that the ancilla register contains only one qubit, the second register contains т qubits, and the last two registers together contain a total of log (N qubits.
Conditioning on 10),, we implement the QPE algorithm with unitary evolution performed through qPCA. Denoting intermediate states as (6s), the resulting state after the QPE algorithm is
R
15)) = Σ dr (rr) (ur) (A2), 10)..
(37)
The binary representation of the eigenvalue X3 can be used to condition (01) rotation around the y axis of angle 0, aresin x in the ancilla register. The eigenvalue estimation and the conditioned rotation correspond to the matrix inversion in (9). After the rotation, the state of the quantum circuit takes the form
n
V'
10), + ( Ci
(2) = Σ dr (u,) [4),, (x2),
Ci + 0²
(1)
(38)
12
X2
The term G1
xo+0² has be smaller than one, this condition is satisfied by an appropriate selection of the constant Ci (Cleve et al., 1998). Finally, it is possible to reverse the operation over the 7 register, which provides the state
R
VI
2
(1h) = Σ
Ar (1)) (ur) 10),
Ci X2
10) +
X + o 11)a
C1
(39)
+ o²
It is important to note that when the ancilla qubit in the state [1),, the state of the qubit registers m and n represents part of the quadrature expected value.
We can estimate the quadrature expected value QBQ with quantum states by introducing the information of the vector X, and the evaluation points y. For this, need additional quantum state named (x/2
11

---

Published in Transactions on Machine Learning Research (02/2025)
with the same number of registers in (1)). By considering the quantum states X Σ m I4 (m)
and ly), En Un In), we use the amplitude encoding scheme to build the state (12) = [X,) ly), 10) 1)
which is normalized. Note the ancilla qubit in the state [1), for (12). This ensures that when we perform
the dot product between (e'n di2). we always obtain the amplitude coefficient corresponding to the ancilla
state [1), of (v)1) as the dot product (0)1), is always zero.
Consider the dot product between the (e))) and (422) states, which takes the form
R
X 12 02 (X Ur) ( ur)n.
W1 1/2) = 0
Σ
(40)
Dividing the dot product by the rotation constant C1, the result corresponds to the expected value QBQ = (tb 4/2) /ei given Eq. (14). The dot product between Iwo stales can be implemented in a quantum computer through a Hadamard test, which is explained in the Appendix A.5. As a result, the expected value in the quadrature can be written in terms of the probability po of the ancilla qubit to be in the state (0) as
2po -1
QBQ
(41)
C1
The variance of the quadrature can be calculated using a similar circuit. After the quantum phase estimation, the circuit is in the intermediate state ((t), now the conditioned rotation (02) has a different. angle
02 = aarcsin
This results in the state
+2
2
(k)) Σ Ar |urm (ur) 122)
C2
10)a +
C2 X X
11)
(42)
Ar Ar +
o²
where the constant 02 satisfies the condition 02 S 1 02. The algorithm proceeds by conditioning the ancilla register to be in the state [1), and including the vector X,. In this case, we need an additional register, with the same length as [m), to store the quantum state (2/) = {,,) By including an additional ancilla register 1 a SWAP test can be implemented between the Xx,) and the (m) register of the circuit. Appendix A.6 provides the detailed steps for implementing the SWAP test on quantum computers. Measuring both
ancillary qubits to be in the quantum state {1), the probability is
R
R
Pr
2
Σ
X2 + o
1
Σ
X2
0z
(N,, v.)) )
(43)
where the second term is proportional to the variance of the quadrature given in Eq. (15), then it can be written as
R
VBQ 0²
Σ
1
2p11
(44)
2 +
giving the Gaussian process quadrature variance. The quantum circuit to estimate the quadrature variance is shown in Fig. 4. Once the quantum computational method for Gaussian quadrature computation has been constructed we are interested in the computational complexity of the algorithm with respect to the classical Gaussian process quadratures. The quantum state preparation subroutines in our algorithm be implemented using the quantum state preparation technique described by Nakaji et al. (2022), which efficiently prepares the quantum state (xx) with a computational complexity of ((poly(log(NMM)) when the dataset consists of real numbers. We then apply qPCA along with QPE, which has a total computational cost ([lo (Schuld et al., 2016). The next step involves the conditional unitary, which has a low computational complexity of (log(()), so we can neglect its computation cost. We perform measurements in the variance circuit before the SWAP test, which can be implemented with amplitude amplification techniques in O(x2). We then employ the Hadamard and SWAP tests, whose complexity is linear in the
12

---

Published in Transactions on Machine Learning Research (02/2025)
0)
(22
QPE
10)
H
QFT
Ingg
xx
(/x)
(N))
(M)
IXxx
10%
H
Figure 4: Quantumn circuit to estimate the quadrature variance. The red gales represent the parts of the algorithm where the qPCA is implemented, meanwhile, the green part envelopes the implementation of the QPE algorithm.
number of qubits; thus, the measurement accounts for only constant factor, which can be ignored. We use two separate quantum circuits, both of which have the same computational complexity and only introduce a constant multiplicative factor of 2 to the total computational complexity, which can be ignored, but allows us to implement more qubits in the numerical simulations. Therefore, the total computational cost estimate the expected value and variance of our algorithm for the quantum Gaussian process quadrature rule Oppoly(log(A M)) log(M)))?==)) On the other hand, the classical version of the GPQ rule requires computational cost of (M)),, which shows that our algorithm is polynomially faster than the classical algorithm.
6 Numerical Simulations
The simulations performed in this paper correspond to executions of quantum circuits in a classical computer that simulate the result that would be obtained on quantum hardware. The classical simulations already pose several challenges for different factors. The QPE algorithm needs several qubits provide reasonable estimates of the cigenvalucs. Morcover, since estimate multiple cigenvalues in this step, it is important to iifferentiate them properly. Implementing the qPCA evolution operator is sensitive to the parameter t. In this case, we select f. = 2 f and modify the value of 8 as suggested by Cleve et al. (1998), following the inequality > X where Amaz is the largest eigenvalue of the decomposition. For a good approximation, should be slightly greater than X²
As an example for simple demonstration purposes, we considered the integral I₁ = So (x) of a simple one-dimensional sinusoidal function f(x) + sin(x), similar to the one used for regression by Farooq et al. (2024), integrated over the interval Ω = [-x, π] with weight function p(z) = 1. We choose Ç within the same range [-T, T.] with I, = to implement the framework outlined in this work. In this domain, the cigenfunctions corresponding to the Laplace operator are the sinusoidal functions 65(x) sin(=(( + L)/2L), each associated with its respective eigenvalue A = (Tj/2L)².
The first demonstration the algorithm was implemented using a constant value of 6 = >2 + = 8 evaluation points, 5 16 qubits to store the cigenvalues, M 4 cigenfunctions approximate the kernel and 10s shots per circuit execution. The simulations were implemented using classical simulator of quantum computer using the QISKIT library (Qiskit contributors, 2023). For the simulations, consider the square exponential kernel in Eq. (3) with hyperparameters of and é= 1, whose spectral density is 5(w)= = of 2 exp (-1a²). The noise of the evaluation points has Gaussian distribution with zero mean and variance o 0.05.
Fig. shows the distribution that estimates the integral In given by the GPQ in Eqs. (6) and (7), the low-rank Hilbert space quadrature in Egs. (9) and (10) and our proposed quantum Hilbert space quadrature
13

---

Published in Transactions on Machine Learning Research (02/2025)
GPQ HSQ
3
Probability density
QHSQ R=1
QUSQ R-2
2
QHSQ R=3
QUSQ R=4
5.6
5.8
6.0
6.2
T
6.4
6.6
Integral value
Figure Estimate of the quadrature for the integral IT The estimation results deliver the expected value and variance of the Gaussian distributions plotted above that approximates the integral. The dotted black plot corresponds to the GPQ, the dashed red plot corresponds to the HSQ and the solid green plots correspond to the estiemates using our QHSQ algorithm with R = 1,2,3.4.
7.5
3.5
GPQ
T
3.0
6.0
HSQ
QUSQ R=1
2.5
Mean
4.5
GPQ
QHSQ R=2
2.0
Variance
QHSQ R=3
HSQ
3.0
QUSQ R=4
1.5
QUIQQ R=1
QHSQ R=2
1.0
1.5
QHSQ R=3
0.5
QHSQ R=4
0.0
0.0
2
8
10
12
14
16
2
4
6
8
10
12
14
16
Number of evaluation points
Number of evaluation points
Figure 6: Expected value and variance of the Gaussian quadrature methods against the number of evaluation points. The dotted black line corresponds to the GPQ, the dashed red to the HSQ and the solid green lines correspond to our proposed QHSQ method with 1,2,344.
method. The distributions given by R 1,2 are quite distant from the integral value, meaning those low-rank approximations do not have enough information approximate the integral. Also, these two distributions have a similar expected value, which is expected since the vector X,, of this problem has X = Xy4 = O. Similarly, the distributions with R = 3, have a similar expected value, this time around the expected value of the integral given by the classical HSQ, showing the effectiveness of our proposed algorithm.
The expected value and variance of the method were plotted in Fig. 6 against the number of evaluation points used for the quadrature, which are symmetrically distributed around = 0. Besides the mumber of evaluation points, simulation parameters are the same the previous example. The implementation of the algorithm susceptible to the parameter occasionally, it can lead wrong results due to the small rotations implemented in the circuit. and the limited number of qubits used to approximate the eigenvalues
14

---

Published in Transactions on Machine Learning Research (02/2025)
X² To avoid outlier results, implemented the algorithm with six different values of 8 = Xmas + with E (0.01, 0.009, 0.008, 0.007, 0.006), and we took the median of these results for each number of evaluation points.
For the quantum implementation, it can be seen that as increases, the expected value approaches the integral real value and also the classical counterpart of the method. It can also be seen that the quantum method has greater fluctuation than the classical methods, mainly attributed to the limited amount of qubits used in the simulations, the finite amount of shots, and the small rotations implemented in the algorithm. On the other hand, can how the variance of the quadratures decreases with the number of evaluation points as expected.
7 Conclusion
In this paper, we introduced a novel quantum algorithm for low-rank Gaussian process quadrature. The method combines the uncertainty quantification properties of Bayesian quadrature methods for numerical integration (O (O'Hagan, 1991; Minka, 2000) with the speedups provided by quantum computation. Our method provides a polynomial complexity reduction compared to the classical GPQ rule, enhancing the solution of analytically intractable integration problems. We have also demonstrated the performance of the method using numerical simulations run on a classical simulator of a quantum computer, which shows that the algorithm works in practice. Our quantum algorithm computes the same solution as obtained from a classical computer but with accelerated speed. The simulation results slightly deviate from the classical GPQ because we use an approximate implementation of the unitary operation for qPCA along with limited number of qubits.
The proposed quantum algorithm is suitable for a fault-tolerant quantum computer with enough quan- tum registers to implement. the algorithm precisely. Recent developments in materials research have shown promisc in the rcalization of fully scalable quantum computers with higher coherence times (Acharya et al., 2024), which opens a window for implementing the method in real hardware. Also, we discussed the sen- sitivity of the method concerning the QPE 8 parameter. However, this drawback can be overcome with advanced quantum simulation techniques (Zulchner & Wille, 2019) that improve the classical demonstration of the method.
Future work could include the optimization of the quantum circuit needed for the algorithm implementation and demonstrations using advancod classical simulation techniques for quantum computers. Besides the well- known data encoding problem in quantum computing, the complexity of the algorithm mainly dominated by the QPE and the qPCA parts of the algorithm. These steps can be reduced using iterative approaches for the QPE algorithm (Smith et al., 2022), allowing it to be parallelized. The qPCA implementation be enhanced using hybrid approach, despite increasing the classical resources needed to implement the algorithm, a variational circuit can be implemented to reduce the complexity of the quantum circuit that is exccuted (Xin et al., 2021). This could enable the algorithm to be exccuted in a noisy intormediato-scale quantum computer.
Author Contributions
C.A. Galvis-Floroz and A. Farooq contributed equally to this work. All the authors contributed to the original idea, writing, and finalizing the paper results.
Acknowledgments
C.A. Galvis-Florez, A. Farooq and Simo Särkkä thank the Research Council of Finland for funding this rescarch (project 350221).
References
Ravi Acharya, Maddison Coke, Mason Adshead, Kexue Li, Barat Achinuq, Rongsheng Cai, A. Baset Gholizadeh, Janet Jacobs, Jessica L. Boland, Sarah J. Haigh, Katie L. Moore, David N. Jamieson, and
15

---

Published in Transactions on Machine Learning Research (02/2025)
Richard J. Curry. Highly 28Si enriched silicon by localized focused ion beam implantation. Communica- tions Materials, 5(1):57, 2024. ISSN 2662-4443. doi: 10. 10.1038//432446-224--00088
George B. Arsken, Hans J. Weber, and Frank E. Harris. Malhemalical Melhods for Physiciiss. Academic Press, Boston, 6th edition, 2005.
Elsevier
Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 270:359 371, 2007.
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters, 114:090502, 2015. doi: 1a.10//Phssleeeeett.111000000000
Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and es- timation. In Quantum Compulation and Information, volume 305, pp. 53 74. American Mathematical Society, Washington D.C., 2002. doi: /01/00//omm/0///////
Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87:167902, 2001.
Abdulkadir Canatar, Evan Peters, Cengiz Pehlevan, Stefan M. Wild, and Ruslan Shaydulin. Bandwidth enables generalization in quantum kernel models. Transactions on Machine Learning Research, 2023.
ISSN 2835-8856.
Almudena Carrera. Vazquez and Stefan Woerner. Efficient state preparation for quantum amplitude estima- tion. Physical Review Applied, 15(3):034027, 2021. doi: 10.1103 Att.s///yyseowwppi........... 15.034027.
Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Pro- ceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454 (1969):339-3) 354, 1998.
Philip J. Davis and Philip Rabinowitz. Methods of numerical inlegration. Computer science and applied mathematics. Academic Press, San Diego, 2nd edition, 1984. ISBN 0122063600.
David P. DiVincezzo Two-bit gates universal for quantum computation. Physical Review A, 51:1015- 5hy.RevA.5111115.
1022, 1995. doi:
Ahmad Farooq, Cristian A. Galvis-Flores and Simo Särkkä. Quantum-assisted Hilbert-space Gaussian process regression. Physical Review A, 109:052410, 2024. doi: 10.1 At...PyloRR.AA.....22......
Lov K. Grover. fast quantum mechanical algorithu for database search. In Proceedings of the Twenly- Eighth Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 212 219, New York, NY, USA, 1996. Association for Computing Machinery.
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems equations. Physical Review Letters, 103:150502, 2009.
Philipp Hennig, Michael A. Osborne, and Hans Kersting. Probabilistic Numerics: Computation as Machine Learning. Cambridge University Press, Padstow Cornwall, 2022.
Toni Karvonen and Simo Särkkä. Classical quadrature rules via Gaussian processes. In 2017 IEEE 27th International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1 6, 2017. doi: 10.1109/
ALLSP.2017. 8168199.
Alexei Y. Kitaev. Quantum measurements and the Abelian stabilizer problem. arXio:9511026, 1995.
Seth Lloyd. Universal quantum simulators. Science, 273(5278))10733-177, 1996. doi: 10.1126/sciencc.277 5278.1073
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631-63) -33333333333-33 2014.
16

---

Published in Transactions on Machine Learning Research (02/2025)
Jorge J. Martinez de Lejarza, Michele Grossi, Leandro Cieri, and Germán Rodrigo. Quantum Fourier iterative amplitude estimation. In 2023 IEEE International Conference Quantum Computing and Engineering (QCE), volume 01, pp. 571 579, 2023. doi: 00.1009/QCU3370022223.0000
Thomas P. Minka. Deriving quadrature rules from Gaussian processes. Technical report, Microsoft Research, Statistics Department, Carnegie Mellon University, 2000. URL attps://wwx. microsoft. cww/co////e///ee /en-us/
srapeeesseaassssa-prressseesss Accessed 19 Feb. 2025.
Kouhei Nakaji, Shumpei Uno, Yohichi Suzuki, Rudy Raymond, Tamiya Onodera, Tomoki Tanaka, Hiroyuki Tezuka, Naoki Mitsuda, and Naoki Yamamoto. Approximate amplitude encoding in shallow paramcterized quantum circuits and its application to financial market indicators. Plysiicul Review Research, 4:023136, 2022.
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniver- sary Edition. Cambridge University Press, Padstow Cornwall, 10th edition, 2011.
Anthony O'Hagan. Bayes Hermite quadrature. Journal of Statistical Planning and Inference, 29(3):245-200 260, 1991.
Qiskit contributors. Qiskit: An open-source framework for quantum computing, 2023. URL https://doi. 025///0....///220d0.777774444 Accessed: 19 Feb. 2025.
Joaquin Quinonero-Candela and Carl E. Rasmussen. A unifying view of sparse approximate Gaussian process regression. Journal of Muchine Learning Research, 6:1939-1999 1959, 2005.
Carl E. Rasmussen, Christopher K. Williams, et al. Gaussian processes for machine learning, 2006.
Maria Schuld and Nathan Killoran. Quantum machine learning in feature Hilbert spaces. Physical review
letters, (2)440044, 2019.
Maria Schuld and Francesco Petruccione. Machine learning with quantum computers. Springer, Cham, 2021.
Maria Schuld, Πya Sinayskiy, and Francesco Petruccione. Prediction by lincar regression on a quantum computer. Physical Review A, 94:022342, 2016.
Peter W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124 134, 1994.
Guoqiang Shu, Zhong Shan, Jinchen Xu, Jic Zhao, and Shuya Wang. A general quantum algorithm for numer- ical integration. Scientific Reports, 14(1):10432, 2024. ISSN 2045-2322. doi:
Joseph G. Smith, Crispin H. W. Barnes, and David R. M. Arvidsson-Shukur. Iterative quantum-phase- estimation protocol for shallow circuits. Physical Review A, 106:062615, 2022.
Arno Solin and Simo Särkkä. Hilbert space methods for reducod-rank Gaussian process regression. Statistics and Computing, 30(2):419-44) 446, 2020.
Masuo Suzuki. Generalized Trotter's formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems. Communications in Mathematical Physics, 51(2):183-190, 1976. ISSN 1432-0916. doi: 10.1007/BF0100934..
Simon Wiedemann, Daniel Hein, Steffen Udluft, and Christian B. Mendl. Quantum policy itcration via amplitude estimation and Grover search towards quantum advantage for reinforcement learning. Trans- actions on Machine Learning Research, 2023. ISSN 2835-8856.
Tao Xin, Liangyu Che, Cheng Xi, Amandoep Singh, Xinfang Nie, Jun Li, Ying Dong, and Dawci Lu. Experimental quantum principal component analysis via parametrized quantum circuits. Physical Review Letters, 126:1 10502, 2021.
17

---

Published in Transactions on Machine Learning Research (02/2025)
Kwangmin Yu, Hyunkyung Lim, and Pooja Rao. Practical numerical integration NISQ devices. In Quantum Information Science, Sensing, and Compulalion XII, volume 11391, pp. 1139106. SPIE, 2020. doi: 10.1117/12.2558200
Alwin Zulehner and Robert Wille. Advanced simulation of quantum computations. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 38(5):848 859, 2019. doi: 10.1109/TCAD. 2018.2834422
A Review of Fundamental Concepts of Quantum Computing
In this section, will review the fundamental concepts used to implement our algorithm, known as the quantum-asiited Hilbert space Gaussian process quadrature rule. We follow and use the symbols and notations as used by Schuld & Petruccione (2021).
A.1 Qubits
The basic unit of quantum computer is the qubit, which is the analog of the bit in classical computers. A single qubit can be either in quantum state [0) = or [1] Moreover, it can also be represented as linear combination of both states, known as superposition, given by (Niclsen & Chuang, 2011)
(g) = a - 11),,
(45)
with a, 3 E C. Moreover, the squared amplitudes |a:3 and |3] correspond to the probability of measuring
the qubit (g) the state (0) or [1) respectively. Then, they satisfy the condition |a|2 + |3] = 1. An n-qubit unentangled quantum system can be represented as the tensor product of single-qubit states
[3) = 9n)) 2 lgn)
(46)
More generally, can be written as the superposition
2
I)) = Σ 1=0
0z 11)
(47)
where a; E C,
and {}i)} represents the computational basis (/0...0) = (0)
12" - 1)}. Interactions between qubits can lead them into entangled states, which play an important role in the development of quantum algorithms and applications of quantum technologies. Entangled states cannot be represented as the product of individual states, for example, an entangled two-qubit quantum state can be represented
V2 (10),, 10), 14) (1)
(
/2 (100) + 111)
(48)
The complete state cannot be written (g1) @ (92), however, it corresponds to the superposition of specific states of the computational basis.
It is important to notice that neither qubit nor in the quantum state has a definite value, but when the state of one qubit is measured, a probabilistic process, then the state of the other qubit completely defined. When the qubit qi measured in specific state, for example, 10), the qubit 9a immediately takes the value (0). The same logic applies when the measurement is performed over the qubit 92.
A.2 Quantum gates
Quantum logic gates are the fundamental building blocks of quantum circuits, whose action on the quantum states defines the dynamics of the circuit. This section follows Schuld & Petruccione (2021) give brief introduction to single and multiqubit gates. Quantum gates are realized through unitary transformation.
18

---

Published in Transactions on Machine Learning Research (02/2025)
Unlike the classical gates, quantum gates reversible. For single qubit, there three fundamental gates known as Pauli matrrices
0 )
0 :
-60 --)
-
Ox
By
(49)
The Pauli X-gate is equivalent to the classical NOT gate for quantum system. This gate flips (0) to (1) and vice versa. This can be represented in matrix form as
Ox (0) = { 1)00 ()) ( = -11)
Oz 11) = ( 0) (
0
1 = (0)
(50)
The Pauli Z-gate introduces a phase of -1 to the (1) state and keeps [0] state unchanged
o= 00 = : - )) - () 10) o. 11) = ( -) - --13)
(51)
Similarly, the Pauli Y gate flips the quantum state and performs a phase flip operation on quantum state
Tg 10) = ( ()) ())(())(1))) =(11).
11] = 0
(: )) ()) -7) -i
(52)
A more general form of single-qubit gates is the rotations around the 2, y, axis of the Bloch sphere Nielsen & Chuang (2011). These rotations are parametrized with respect to an angle and have the form
(o( = 18
( cos(
-ssin
- sin
cos(
6
cos( 0 sin
sin( ( cos( ?)
(0) -ig0v
(53)
(0) c -1f00
The previous rotations defined general rotation of a qubit parametrized by three angles given by U() (2( R... ())
cos & cl sin @
- sin &
(54)
el(d+)) cos
Besides single qubit gates, multiqubit gates act over multiple qubits through unitary quantum operations. These gates usually responsible for entanglement between qubits. The Controlled-NOT (CNOT) gate is the most common two-qubit quantum gate. The quantum state is changed only when the control qubit is in the 11) state and remains unchanged if the control qubit is in the (0) state. The matrix representation of the NoT gate defined as follows
0
0
CNOT (1
(55)
0
0
0
0
The operation of the CNOT gate two-qubit quantum states is given by
CNOT (00) J00). CNOT [01), CNOT [10) [11), CNOT [11) [10)
(56)
The concept of controlled gates is extended controlled general rotations, which can be represented in a matrix of the form
0
0 - e i2 sin
0
CU(O, (,) - 10) //)0/+1)))0 ()
(57)
cos
Gld sin
((++a) cos
2
19

---

Published in Transactions on Machine Learning Research (02/2025)
A SWAP gate is often used in quantum algorithms to exchange qubits in two quantum registers. The SWAP
gate is given by
1
0
SW AP
(58)
0
0
0
Acting over two arbitrary states (0) (v)) it will give
SW AP (b) (b)
(4b) (0)
(59)
We have reviewed some the most common quantum gates, however with one two-qubit gate and four single-qubit gales, possible to build any multiqubit quantum circuit (DiVincenzo, 1995).
A.3 Quantum measurements
We need to perform measurements to retrieve quantum information from quantum state (v)) The outcomes of these measurements are random, whose probabilities are given by the elementary operators M, = lox) (di) through Born's rule (Niclsen & Chuang, 2011)
P. (v) M,
(60)
The measurement operators are collection of rank-1 projectors that sum to the identity Σ, E,M, I. Generally, we take the computational basis, which is orthonormal, to define the measurement operators for different quantum algorithms.
Similarly, we can perform partial measurements over some fraction of the qubits that compose the system. For example, performing measurements only on the first qubit in the (0) basis gives
Po = (vb110) (0) @ I.... @ II [
(61)
Partial measurements are used in the Hadamard and SWAP tests to estimate the inner product between quantum states.
A.4 Amplitude encoding
The amplitude encoding scheme encodes each element of the normalized vector into coefficient of the quantum state. Suppose we have a vector x = [+1, ... T2n), where x E C We first normalize the vector such that Ei" |z; = and encode the vector into the quantum state (Schuld & Petruccione, 2021)
2
[xx)
Σ
xz (t)
(62)
1=
We also encode the matrix A C2" x2" with entries an that fulfill Σig ||a 1|2 = in similar fashion to
2 2"-12"
Σ
oig (b) li)
(63)
with the enlarged Hilbert space accordingly. The index registers (t), (j) refer to the ith row and the jth column the matrix A.
A.5 Hadamard test
The Hadamard test calculates the inner product between two states along with correct signs. The additional overhcad with the Hadamard test that the ancilla qubit is entangled with both quantum states (ı/) and (2) as follows (Schuld & Petruccione, 2021):
(vb)) = / (10) (x1) + (L) ((2)).
(64)
20

---

Published in Transactions on Machine Learning Research (02/2025)
Once we have the state available in this entangled form, we then apply Hadamard gate to the ancilla qubit, resulting in
1 2 @ (1$1) - l2/2)
(x) (0) @ (111) + (+2))
(65)
The real and imaginary parts of the inner product After this, we measure on the computational basis. between the two quantum states are given by
Re((vil))2) - 2po - 1, Im(((il(22) = -1 2po-
(66)
When the states are real, the calculation of the real part becomes the actual inner product between the two quantum states.
A.6 SWAP test
The SWAP test in quantum computers is used to extract the square of the absolute value of the inner product between two quantum states (&1) and |x22) (Schuld & Petruccione, 2021). Suppose that we are given these two quantum states the tensor product form (wh1) [1/2). We start by adding an extra ancilla qubit (0) (xh)) (222)- Then, we apply Hadamard gate the ancilla qubit, resulting the following quantum state
1
/2 (10) + (1)) (un) 1122)
/2 (10) (1))) (8/)) + (1) (4/) (12)).
(67)
Next, we apply the swap operation between the two states conditioned on the ancilla qubit being in the quantum state 1) as
1 (10) W1) (2) [L) (b11) (12))
Controlled
V2 (10)
1
(111 (x2) (1) (w22 (ch)).
(68)
SWAP
Applying another Hadamard gate on the ancilla qubit we have
1 (10) @ ((1)) (1/2) + (e/2) lbb1)) + (1) @ (1/1) (22)) - (1/2) (xaa)))
(69)
2
When we measure the ancilla qubit, the probability of measuring the state (0) is
1 + (w/2 (2)
Po 2
(70)
This method evaluates the inner product, however, the squared of the absolute value does not allow us to estimate the sign of the inner product.
21


Reviews:
[{"review_id": "wgo9pXYdbP", "reviewer": "Reviewer_HaXP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThe paper is structure-wise. Sections 2 and 3 are quite useful for readers to get the background information.\n\nThe paper provides most of the math details, but it could be improved by adding intuitive descriptions to help readers understand (see requested changes)\n\n### Weakness\nIt seems that the quantum algorithm doesn't outperform classical algorithms significantly. For example, Fig. 6 shows the QHSQ (R=4) deviates more from the mean than GPQ. This makes me doubt whether it is necessary to consider complicated quantum algorithms that need to be implemented by quantum computers that are still far from mature. I think some discussions are needed.\n\nAlso, from the Intro and Conclusion, it is not easy to distinguish the real contribution of the present study. It looks like the current study is a combination of recent quantum techniques. Is it possible the authors also compare the proposed quantum algorithm with other quantum algorithms? \n\nMinor:\n- Page 1, HHL: please provide its full name.\n\n- Fig. 1 caption: The complexity of FFT is $\\mathcal{O}(n \\log n)$, while the caption says it is $\\mathcal{O}(n2^n)$. Did I misunderstand something here?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a quantum algorithm for Gaussian process quadrature problems, as a modification of a recently developed low-rank quantum Gaussian process regression algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Writing: To help general ML readers understand math, it would be better to explain in more detail the binary representation of quantum states, e.g., how Eq. 17 can be converted into Eq. 20 (I can vaguely figure out the math derivatios there but still not very sure), $\\ket{j_1} = \\ket{0} + e^{2\\pi i0.j_1} \\ket{1}$ in Eq. 21.\n\n- What does quantum register mean? Please explain.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "y0SescVqev", "reviewer": "Reviewer_GMVh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The implementation of the HSQ in quantum computer. \nIntegration of the input setting algorithm from Nakaji et al. is a nice complexity reduction. \n\nSometimes the used language is a bit unclear making the paper reading a bit difficult. For instance, page 9, \"Conditioning on the second register, we implement....\" should probably be for better understanding \"Conditioning on the $\\vert0\\rangle_\\tau$, we implement....\"\n\nAccording to the authors, when one of the resulting qubit register is $\\vert1\\rangle_a$ the results can be retrieved and contains the expected value. However what happens when the computation is finished and the indicator register is $\\vert0\\rangle_a$?\n\nDoes the computation of the expected value and of the variance require two separate experiments or can it be implemented as a part of the same quantum circuits?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides the details on implementation of the Gaussian Process Quadrature (GPQ) on a quantum computer. The paper is well written and is clear about the achievements. The main contributions of this work are as follows:\n\n1 - detailed implementation of the GPQ on a quantum computer using the phase estimation approach called QHSQ\n\n2 - verification of the analytic results on small scale simulation\n\n3 - detailed derivation of the whole GPQ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I feel that while the paper is complete and self-contained, the transition between the existing HSQ to QHSQ was not straight forward. I would highly appreciate if there was a clear step by step outline of the classical vs the quantum algorithm in the paper. \n\nSome more explanations of the steps of the algorithms would be very beneficial for understanding", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tJd5wujKwv", "reviewer": "Reviewer_b6QV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n-----------------\n\n- The paper seems well written and illustrated\n-  The idea and speedup for this important problem is interesting\n\nWeaknesses\n-----------------\n- Despite the extensive background the paper is hard to understand, at least for me. I suspect\nit will be similar for other researchers with ML/Stats background. \n- I am not entirely sure how interesting this topic is for the TMLR audience, although there is one earlier paper in TMLR on the quantum advantage of Reinforcement Learning, so there appears to be some interest.\n- I am not sure how much contribution the paper delivers compared to Farooq et al (2024), see the requested changes comment below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper develops a novel algorithm to perform numerical integration using Gaussian process quadrature rules on a quantum computer. After providing background on Hilbert space approximations for the Gaussian Process as well as the background on quantum algorithms, the paper develops the quantum Hilbert space low-rank Gaussian process quadrature and shows its reduction in complexity compared to methods on a classical computer.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My comments mainly concern the readability of the paper.\n\n- Maybe this is a naive question, but what is the intuitive reason for the reduced complexity of the quantum algorithm? I guess it has to do with the ability of quantum states to be in a superposition, but it might be helpful to spell this out for laymen like me.\n\n- The introduction talks about complexity reduction without explaining kappa, s, and epsilon. In general, given all the notation, a small table at the beginning summarizing the most important symbols might be helpful. This table could focus mainly on symbols related to the quantum algorithm, since I think the audience of TMLR is more familiar with the notation used in Section 2. \n\n- What exactly is different from the previous paper by Farooq et al. (2024)? It might be useful to flesh this out more.\n\n- The |j> notation is extremely confusing to me, and while the appendix is helpful, I think this should be explained when it first appears in Section 3.1.\n\n- I think equation (27) should be equation (26).\n\n- Is it possible to make more references to section 2 in section 4 to try to make it as clear as possible which steps in the quantum algorithm roughly correspond to a calculation in calculating (14) and (15)?", "broader_impact_concerns": "No Concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were unanimous in recommending acceptance of the paper. The reviewers commended the paper for being well-written and illustrated. It provides ample background material in order to improve accessibility for members of the community unfamiliar with quantum algorithms. The authors diligently addressed the questions of the reviewers and significantly improved readability during the revision process. One reviewer commented that the paper is "solid" and a "serious piece of work and as such it merits to be accepted".
Decision: Accept (poster)