Quantum Semi-Supervised Kernel Learning
Authors: Seyran Saeedi
Aliakbar Panahi
Tom Arodz
Venue:  (2020)
Keywords: quantum machine learning
semi-supervised learning
support vector machines

Abstract: Quantum machine learning methods have the potential to facilitate learning using extremely large datasets. While the availability of data for training machine learning models is steadily increasing, oftentimes it is much easier to collect feature vectors that to obtain the corresponding labels. One of the approaches for addressing this issue is to use semi-supervised learning, which leverages not only the labeled samples, but also unlabeled feature vectors. Here, we present a quantum machine learning algorithm for training Semi-Supervised Kernel Support Vector Machines. The algorithm uses recent advances in quantum sample-based Hamiltonian simulation to extend the existing Quantum LS-SVM algorithm to handle the semi-supervised term in the loss, while maintaining the same quantum speedup as the Quantum LS-SVM.

Under review as a conference paper at ICLR 2020
QUANTUM SEMI-SUPERVISER KERNEL LEARNING
Anonymous authors
Paper under double-biee blind review
ABSTRACT
Quantum machine learning methods have the potential to facilitate learning us- ing extremely large datasets. While the availability of data for training machine learning models is steadily increasing, oftentimes it is much easier to collect fea- ture vectors that obtain the corresponding labels. One of the approaches for ad- dressing this issue is to use semi-supervised learning, which leverages not only the labeled samples, but also unlabeled feature vectors. Here, we present a quantum machine learning algorithm for training Semi-Supervised Kernel Support Vector Machines. The algorithm uses recent advances in quantum sample-based Hamilto- nian simulation to extend the existing Quantum LS-SVM algorithm to handle the semi-supervised term the loss, while maintaining the same quantum speedup as the Quantum LS-SVM.
INTRODUCTION
Data sets used for training machine learning models are becoming increasingly large, leading to continued interest in fast methods for solving large-scale classification problems. One of the ap- proaches being explored is training the predictive model using quantum algorithm that has access to the training set stored in quantum-accessible memory. In parallel to research on efficient architec- tures for quantum memory (Blencowe) 2010), work quantum machine learning algorithms and on quantum learning theory is under way (see for example Refs. (Biamonte et al. [2017] Dunjko & Briegel| 2018; [Scuuld & Petruccione (2018) and (Arunachalam & de Wolf, [2017) for review).
An early example of this approach is Quantum LS-SVM (Rebentrost et al. (014a), which achieves exponential speedup compared to classical LS-SVM algorithm. Quantum LS-SVM uses quadratic least-squares loss and squared-T. regularizer, and the optimization problem can be solved using the seminal HHL (Harrow et al. (2099) algorithm for solving quantum linear systems of equations. While progress has been made quantum algorithms for supervised learning, it has been recently advocated that the focus should shift to unsupervised and semi-supervised setting (Perdomo-Oree et al. 2018).
In many domains, the most laborious part of assembling a training set is the collection of sample labels. Thus, in many scenarios, in addition the labeled training of size m we have access to many more feature vectors with missing labels. One way of utilizing these additional data points improve the classification model is through semi-supervised learning. In semi-supervised learn- ing, we are given m observations Ii, Zm drawn from the marginal distribution p(z), where the I m) first data points come with labels yI,..., V1 drawn from conditional distribution p(y (r)) Semi-supervised learning algorithms exploit the underlying distribution of the data to improve clas- sification accuracy on unseen samples. In the approach considered here, the training samples are connected by a graph that captures their similarity.
Here, we introduce quantum algorithm for semi-supervised training of a kernel support vector ma- chine classification model. We start with the existing Quantum LS-SVM (Rebentrost et al.) (0044), and use techniques from sample-based Hamiltonian simulation (Kimmel et al.) 2017) to add a semi- supervised term based on Laplacian SVM (Melacci & Belkin 2011). As is standard in quantum machine learning (Li et al. 2019). the algorithm accesses training points and the adjacency matrix of the graph connecting samples via quantum oracle. We show that, with respect the oracle, the proposed algorithm achieves the same quantum speedup as LS-SVM, that is, adding the semi- supervised term does not lead to increased computational complexity.

---

Under review as a conference paper at ICLR 2020
2
PRELIMINARIES
2.1 SEMI-SUPERVISED LEAST-SQUARES KERNEL SUPPORT VECTOR MACHINES.
Consider problem where we are aiming find predictors h(x) that functions from a RKHS defined by kernel K. In Semi-Supervised LS-SVMs in RKHS, we are looking for function h E H that minimizes
min NERLDER
2 (y - (h(z;) + b)) Σ 1=1
2 |1
where y is a user define constant allowing for adjusting regularization strength. The last term captures the squared norm of the graph gradient on the graph G that contains all training samples as vertices, and expresses similarity between samples through, possibly edges Ga,e
Gh h,)² h,,2 h2 Lh, -
1
2
where hy is the function value h(x;) for the vertex corresponding to training point 2,, and L is the combinatorial graph Laplacian matrix such that [[r,j] D3 Gi.j-
The Representer Theorem states that if H is RKHS defined by kernel K X X - R, then the solution minimizing the problem above achieved for a function that uses only the representers of the training points, that is, function of the form h(x) شラ=1 Ka -EiT (,K( (æ,, Thus, translate the problem from RKHS into constrained quadratic optimization problem over finite, real vectors
1 _ KKLK E -e i=1
1
min c.E.b
s.t. 1 V/
b+ Σ
E:
2
where S m is the number of training points with labels (these are grouped at the beginning of the training set), and i = Kr, since function h is defined using representers Kg,- The semi-supervised term, the squared norm of the graph gradient of h, 1/2] Vh [2. penalizes large changes of function h over edges of graph G. In defining the kernel K and the Laplacian L and in the regularization terms we use all m samples. On the other hand, in calculating the empirical quadratic loss we only use the first samples.
The solution to the Semi- Semi-Supervised LS-SVMs is given by solving the following (m + 1) x +1 system of linear equations
0 1
1sT
0 y
K + KLK 11
where y (yi,..., Vm T. (1,..., 1)T, is identity matrix, K is kernel matrix, L is the graph Laplacian matrix, 7 is hyperparameter and a (a1,,.., 0mm)² is the vector of Lagrangian multi- pliers.
2.2 QUANTUM COMPUTING AND QUANTUM LS-SVM
Quantum computers are devices which perform computing according to the laws of quantum me- chanics, mathematical framework for describing physical theories, in language of linear algebra.
Quantum Systems. Any isolated, closed quantum physical system be fully described by unit-norm vector in a complex Hilbert space appropriate for that system; in quantum computing, the space always finite-dimeniooal, Cd. In quantum mechanics and quantum computing, Dirac notation for linear algebra is commonly used. In Dirac notation, a vector x E Cd and its complex conjugate xT, which represents a functional Cd - R, are denoted by xx) (called ket) and (xl (called bra), respectively. We call (le.) the computational basis, where lex) = (0, 1,...)' with exactly one entry in the i-th position. Any iv) (ei,..., VT)TT can be written as v) = Σi_ ayee);; coefficient v; C are called probability amplitudes. Any unit vector (x) Cd describes d-level
2

---

Under review as a conference paper at ICLR 2020
quantum state. Such system is called pure state. An inner product of [2))_122 C is written as (x) 12). A two-level quantum state (&b) = a 0) + B[1), where [0] = (1.0)', = (0. 1)" and a,3 E C, |a|2 + |,8|, is called a quantum bit, or qubit for short. When both and / are nonzero, we say (0)) is in a superposition of the computational basis 0) and (1); the two superposition states
|+) (10) + [1)) and |-)
(10) 11)) are very common in quantum computing.
V2
A composite quantum state of two distinct quantum systems (21) E Cd and (z2) C is described (22) E
as tensor product of quantum states (T) @
Cddy
( Cde Thus, a state of an n--ubii system is
vector in the tensor product space (C2) C2 C @ C², and is written as Ei-o -2 a, [i),
where i is expressed using its binary representation; for example for n. = 4, we have (2) = [0010]
(0) & 10) 2 (1) (0).
Transforming and Measuring Quantum States. Quantum operations manipulate quantum states in order to obtain some desired final state. Two types of manipulation of quantum system are al- lowed by laws of physics: unitary operators and measurements. Quantum measurement, if done in the computational basis, stochastically transforms the state of the system into one of the computa-
tional basis states, based on squared magnitudes of probability amplitudes; that is, V2
(10) + (1))
will result in (0) and [1) with equal chance. Unitary operators are deterministic, invertible, norm- preserving linear transforms. A unitary operator U models a transformation of a quantum state (u) to Ju) = 2/)u.. Note that (d/u1) + ld [ = 24 (luı) + u2)). applying a unitary to a superposition of states has the same effect as applying it separately to element of the superposition. In quan- tum circuit model unitary transformations are referred to as quantum gates for example, one of the most common gates, the single-qubit Hadamard gate, is unitary operator represented in the computational basis by the matrix
1 V2 (1
H =
Note that H|0) = |+) and 1111==1-
Quantum Input Model. Quantum computation typically starts from all qubits in [0] state. To perform computation, access to input data is needed. In quantum computing, input is typically given by a unitary operator that transforms the initial state into the desired imput state for the computation such unitaries are commonly referred to as oracles, and the computational complexity of quantum algorithms is typically measured with access to an oracle as the unit. For problems involving large amounts of input data, such for quantum machine learning algorithms, random access memory is often assumed, Quantum random access memory (qRAM) uses log N qubits to address any quantum superposition of N memory cell which may contains either quantum classical information. For example, ARAM allows accessing classical data entries xa! in quantum superposition by transformation
oracle that abstracts
i,
GRAM
mmp
where |x:)) is a binary representation up to given precision. Several approaches for creating quan- tum RAM are being considered (Giovannetti al.] 2008) AAumachalam al.) | Biamonte al.) 2017), but it is still an open challenge, and subtle differences in qRAM architecture may erase any gains in computational complexity of a quantum algorithm Aaronson (2015).
Quantum Linear Systems of Equations. Given an input matrix A E Ca and a vector b E C", the goal of linear system of equations problem is finding x C" such that Ar b. When A is Hermitian and full rank, the unique solution is = A- If A is not full rank matrix then A is replaced by the Moore-Penrose pseudo-invend inverse.. HHL algorithm introduced an analogous problem in quantum setting: assuming efficient algorithm for preparing b as quantum state b = Σ b using [log n + qubits, the algorithm applies quantum subroutines of phase estimation, controlled rotation, and inverse of phase estimation to obtain the state
A
|x) =
(3)
AA-1 II
3

---

Under review as a conference paper at ICLR 2020
Intuitively and at the risk of ovep-liigl,,ying, HHL algorithm works follows: if A has spec- tral decomposition A Ei=1 Nmaay (where X and o are corresponding eigenvalues and eigen-
1
A U1- The vector b also be written as the linear combination of the A's eigenvectors es as b = Eim1 Bru; (we are not required to compute 3.). Then A- Ei=1 1 B. In general A and A-1 not unitary (unless all A's eigenvalues
states of A); then A-1 maps Aee +
have unit magnitude), therefore we are not able to apply A-1 directly on 1b). However, since U edd = _i= ".a unitary and has the same eigenvectors A and A one can im- plement U and powers of U on a quantum computer by Hamiltonian simulation techniques; clearly for any expected speed-up, one need to enact eA efficiently. The HHL algorithm uses the phase estimation subroutine to estimate an approximation of X, up small emror. The Next step com- putes a conditional rotation on the approximated value of X and an auxiliary qubit (0) and outputs
1). The last step involves the inverse of phase estimation and quantum measure-
X;
1
ment for getting rid of garbage qubits and outputs our desired state (.:) 1- = Σ 3 U/-
Density Operators. Density operator formalism is an alternative formulation for quantum me- chanics that allows probabilistic mixtures of pure states, more generally referred to as mixed states. mixed state that describes an ensemble {pi, ( is written as
k
Pa (Avl)
(4)
where Σ Ps = forms probability distribution and p is called density operator, which in
iimte-dimensional system, in computational basis, is semi-definite positive matrix with Tr(p) = 1.
A unitary operator l/ maps quantum state expressed as density operator p to Uplt' where Ltt is the complex conjugate of the operator U.
Partial Trace of Composite Quantum System. Consider two-part quantum system in state described by tensor product two density operators p 2 a. A partial trace, tracing out the second part of the quantum system, is defined as the linear operator that leaves the first part of the system in a state Tr (p 8 σ) = ptr (o), where Tr (a) is the trace of the matrix a.
To obtain Kernel matrix K as density matrix, quantum LS-SVN (Rebentrost et al. 2014b) relies on partial trace, and on a quantum oracle that can convert, in superposition, each data point {I, [m (x:)e [t), where (xx)e refers to the /th feature value in data point 24 and assuming the oracle is given 2 || and ys+ Vector of the labels is given in the same fashion as (v) Tyll Exe ya li). For preparation the normalized Kernel matrix K' (ī(]] K where K > X, need to prepare quantum state combining all data points in quantum superposition (X)
n; E TR& to a quantum state (z;) = Ix
Σnn (i) & || (zi). The normalized Kernel matrix is obtained
1 1 by discarding the training set state,
K' = Trx((()) = E xe
Σ 1-=1
(,,
(5)
The approach used above to construct density matrix corresponding to linear kernel matrix can be extended to polynomial kernels (Rebentrost et al. 2014b).
LMR Technique for Density Operator Exponentiation. In HHL-bbasdd quantum machine learn- ing algorithms including in the method proposed here, matrix A for the Hamiltonian simulation within the HHL algorithm is based on data. For example, A can contain the kernel matrix K cap- tured in the quantum system as a density matrix. Then, one need to be able to efficiently compute -K where is scaled by the trace of kernel matrix. Since K is not sparse, a strategy similar to (Lloyd et al. 2014) is adapted for the exponentiation of non-sparse density matrix:
Tri {e- (C-iSS((K 60 (900 = -ii(K, o) O (AP) x -K 0e KAt
4

---

Under review as a conference paper at ICLR 2020
where S Ex, (0 & (i] is the swap operator and the facts Tri [S(K Ko and Th {(K &0 (0))} o used. The equation (6) summarizes the LMR technique: approximating o-ikA' up to enror 0( is equivalent to simulating a swap operator S, applying it to the state K and discarding the first system by taking partial trace operation. Since the swap operator is sparse, its simulation is efficient. Therefore the LMR trick provides an efficient way to approximate exponentiation of non-sparse density matrix.
Quantum LS-SVM. Quantum LS-SVM (Rebentrost al. 2014b) uses partial trace construct density operator corresponding to the kernel matrix K. Once the kernel matrix K becomes available as a density operator, the quantum LS-SVM proceeds by applying the HHL algorithm for solving the system of linear equations associated with LS-LSVM, using the LMR technique for performing the density operator exponentiation iKAt where the density matrix K encodes the kernel matrix.
QUANTUM SEMI-SUPERVISED LEAST SQUARE SVM.
Semi- Semi--upervised Least Square SVM involves solving the following system of linear equations
b 0 a
1 K
0
0 y
A-
1
+
y
In quantum setting the task is to generate |b, a) = 10, y). where the normalized Å A
Tr(A) The linear system differs from the one in LS-SVM in that instead of K, have K + KLK. While this difference is of little significance for classical solvers, in quantum systems we cannot just multiply and then add the matrices and then apply quantum LS-SVM are limited by the unitary nature of quantum transfornations.
In order to obtain the solution to the quantum Semi- Supervised Least Square SVM, will the following steps. First, we will read in the graph information to obtain scaled graph Laplacian matrix density operator. Next, will polynomial Hermitian exponentiation for computing the matrix inverse (K - KLK)
3.1 QUANTUM INPUT MODEL FOR GRAPH LAPLACIAN
In the semi-supervised model used here, we assume that we have information on the similarity of the training samples, in a form graph that uses n edges to connect similar training samples, represented vertices. We assume that for each sample, G' contains its h most similar other samples, that is, the degree of each vertex is d. To have the graph available as a quantum density operator, observe that the graph Laplacian I is the Gram matrix of the of the m graph incidence matrix G₁, L GfG?" We assume oracle access to the graph adjacency list, allowing us construct, in superposition, states corresponding to rows of the graph incidence matrix G₁
lui) Σ Grli,dltt).
That is, state (w:) has probability amplitude v/2 for each edge [t) incident with vertex and null probability amplitude for all other edges. In superposition, we prepare a quantum state combining rows of the incidence matrix for all vertices, to obtain
m
G1)
/m
The graph Laplacian matrix L, composed of inner products of the rows of Gr, is obtained by dis- carding the second part of the system,
m Σ 1-=1
1 m Σ (oule)))))(1
(8)
md
5

---

Under review as a conference paper at ICLR 2020
3.2 POLYNOMIAL HERMITIAN EXPONENTIATION FOR SEMI SUPERVISED LEARNING
For computing the matrix inverse (K + KLK) on a quantum computer that runs our quan- tum machine algorithm and HHL algorithm
subroutine, need to efficiently compute -KKKKLK)A + For this purpose adapt the generalized LMR technique for simulating Hermitian polynomials proposed (Kimmel et al.) 2017) to the specific case of e (K +KL)) Simulation of eiikst follows from the original LMR algorithm, and therefore we focus here only simulation e T. The final dynamics (K + KKLK) can be obtained by sampling from the two separate output states for e e and e AiK
Simulating eiKLKAt, Let ((H) denote the space of density operators associated with state space H. Let Kt, K, L. E D(H) be the density operators associated with the kernel matrix and the Lapla- cian, respectively. We will need two separate systems with the kernel matrix K, distinguish between them we will denote the first as K and the second as K; since K is real and symmetric, these are indeed equal. The kernel and Laplacian matrices Kt, K, are not sparse therefore we adapt the generalized LMR technique for simulating Hermitian polynomials for our specific case B KTL..
For adapting the generalized LMR technique to our problem we need to generate quantum state (0) & p" + +11 & p" with Tr(p" + p" = 1, such that
Tri Th' {e fe- is ()) e 1 }} - il 0 e
iBt 00 iBt O(A)),
(9)
where B = p" p" controlled partial swap in the forward (+S) and backward direction (-S) in time, and
= + KKLK = KLK and S' = 10) [1) @ (-S) is
-is'
10)00| & E -SA + [1) @ U
Therefore with one copy of p', we obtain the simulation of e -BA up to error O(A²). If we choose the time slice A = 8/1 and repeating the above procedure for (² times, we are able to simulate e-iBt up to error (6)) using O /8) copies of p'.
Generating p' (0) @ p² + |1] @ p" Figure shows the quantum circuit for creating p' [0)(0) @ p + [1) (1 @ p" such that Tr Trpp" p²
and B p" p" = KLK.
HX{+|
H
K
L
K
Figure 1: Quantum cireuit for creating p' = left-to-right. Each wire at left shows its corresponding input state. The vertical rectangle denotes the cyclic permutation operator P on K, T,, K defined in {TO). H is the Hadamard gate, and the waste bins show partial trace. The measurement on the first quantum state is in computational basis.
@ p The circuit is to be read from
The analysis of the steps preformed by the circuit depicted in Fig is as follows. Let P be the cyclic f2).. In operator form
permutation of three copies of H. that operates as P [j,, fh. can be written as
dim Ha
P
Σ
lis) Ki
(ix) (ial Ø lia) (ja
(10)

---

Under review as a conference paper at ICLR 2020
The input state to the circuit depicted in Fig. Dis
HHHH@KKSLOK
E
(.E)).1))
Applying on Kt, L, K gives
I == [10 (o) & K &LocLLK++ (1 @ (K' & P
2
+ (1) & (k & a K) + [I) & ( @ P
After discarding the third and second register sequentially by applying corresponding partial trace operators, we get
1 1 kt + 10)(1) @ KKLKK + 11)00 @ &KLK* + +11)(1| @ 2 K,
1I = Tr, [Tr((]] = 10) (0) @
2
2
in this step KLK term where the last line obtained from
Tre
Tr'
K
L
K) P|] KILK,
Tre Tr'
[P(Kt
X ② K)]] = KLK!,
Tr2
[Trs
[P(KT & L. 0 K) PJ] = K.
After applying a Hadamard gate H / [10) + [1) + (10) - (1)) on the first qubit of II, we
get
III H @ ( =1=
1 Kt (10)(0) - (0) [1)00| - (1x) 1 KILK
(10) + |0) [1)0| (1)
2
+ (10)(0) + |0| - (L) & .KLKt + (10)(0) - [0) - (1) +1) (1)(L) & 2
1
2
|o @
1
kt + 1/
kt LK + KKLK + t K
1
1
+ (1)
1
(1
1
KILK
LK 1 _=_KK"
2
2
2
2
2
2
2
+ (1)
1 2
Kt + KILK 1 KLKt - 2 k
1 2
)
+ [1) 8
-
1
Kt
1
1 KILK KLKt + =
1
2
The last step is applying a measurement computational basis (10)00,|11)(1) on the first register to obtain our desired state p'.
IV 10)
1 1/2
kt
L kt KILK 1
KLKt + +/(k)
1
1 1xxt - _1 KKLK* k
+11)(11
@ 2
We can that by defining 6" 1 KKILK + KKLK - 1K) and P"
( kK KKL + K) the final state in the form of p where Tr(p" + p² = 1, and we obtain p" - p" 3 ktLK + KKLKK = B.
Now with having the output state p' we are ready to apply the generalized LMR in 9 to sim- ulate e LiKLKAt ik LK up to error O(A2). Comparing the LMR technique in equation (6) with the generalized LMR for the spacial case of K LK in equation (9) we approximating up to error (At?)) is equivalent to simulating the controlled partial swap op-
erator S". applying it to the state p' @ and discarding the third and first systems by taking partial trace operations, respectively. Since S' also sparse, and its simulation is efficient, the generalized LMR technique offers efficient approach for simulating e LKLKA
7

---

Under review as a conference paper at ICLR 2020
Algorithm Quantuu Semi-Supervised LS-SVM
Input: The datapoint set
with the first data points labeled and the rest unlabeled,
(V1,.... V1) and the graph G
Output: The classifier |a, bj = A A-1ly) ly)
I: Quantum data preparation. Encode classical data points into quantum data points using + (X)
quantum oracles Oz
m
x; (x)) and
=
y (g).
2: Quantum Laplacian preparation. Prepare quantum density matrix using oracle access to G. Matrix inversion. Compute the matrix inversion |a, b) A via HHL algorithm. A
3:
quantum circuit for the HHL algorithm has three main steps:
4:
Phase estimation, including efficient Hamiltonian simulation involving KLK (Section 3.2) Controlled rotation
5:
6: Uncomputing
7:
Classification. Based on Swap test algorithm, same as in Quantum LS-SVM.
3.3 QUANTUM SEMI-SUPERVISED LS-SVM ALGORITIM AND ITS COMPLEXITY
The quantum LS LS-SVM in (Rebentrost et al. 2014b) offers exponential speedup Ollog mp) over the classical time complexity for solving SVM as a quadratic problem, which requires time (log(e=)) poly((, m)), where é is the desired error. The exponential speedup in occurs as the result of fast quantum computing of kernel matrix, and relies on the existence of efficient oracle ac- cess to data. The speedup on m is due to applying quantum matrix inversion for solving LS-SVM, which is inherently due to fast algorithm for exponentiation of a resulting non-sparse matrix. Our algorithm introduces two additional steps: preparing the Laplacian density matrix, and Hamiltonian simulation for KLK. The first step involves oracle access to a sparse graph adjacency list represen- tation, which is at least efficient the oracle access non-sparse data points. The Hamiltonian simulation involves simulating a sparse conditional partial swap operator, which results an efficient strategy for applying e e time (log (m) At). where the notation Ô hides more slowly growing factors in the simulation (Berry al. 2007
3.4 COMPARISON WITH ALTERNATIVE APPROACHES
Considerable effort has been devoted into designing fast classical algorithms for training SVMs. The decomposition--asse based methods such as SMO (Platt 1998) are able to efficiently manage problems with large number features p. but their computational complexities are super-linear in m. Other training strategies (Suykens & Vandewalle 1999| Fung & Mangasarian, 2005| Keerthi & DeCoste, 2005) are linear in m but scale quadratically y in in the worst case. The Pegasos algorithm (Shalev- Shwartz et al., 2011) for non-linear kernel improves the complexity to Ô (m/ ()e)) where X, and the regularization parameter of SVM and the error of the solution, respectively.
Beyond the classical realm, three quantum algorithms for training linear models have been proposed, the quantum LS-SVM that involves L2 regularizer (Rebentrost et al., 2014a), recently proposed Quantum Sparse SVM which is limited to a linear kernel (Arodz & Saeedi] 2019). and quantum training algorithm that solves maximin problem resulting from maximum not average loss over the training set (Li et al. 2019)
REFERENCES
Scott Aaronson. Read the fine print. Nature Physics, 11(4):291, 2015.
Tom Arodz and Seyran Saeedi. Quantum sparse support vector machines. arXiv preprint 17Xiv:1902.01879, 2019.
Srinivasan Arunachalam and Ronald de Wolf. A survey quantum learning theory. ACM SIGACT News, 48(2):41-67, 2017.
8

---

Under review as a conference paper at ICLR 2020
Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O O'Cono, Michele Mosca, and Priyaa Varshinee Srinivasan. On the robustness of bucket brigade quantum RAM. New Jour- nal of Physics, 17(12):123010 2015.
Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C Sanders. Efficient quantum algo- rithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 270(2): 359-371, 2007.
Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning, Nature, 549(7671); 1):01)))9999, 2017.
Miles Blencowe. Quantum computing: Quantum RAM. Nature, 468(7320):44, 2010.
Vedran Dunjko and Hans J Briegel. Machine learning & artificial intelligence in the quantum do-
main: a review of recent progress, Reports on Progress in Physics, 81(7):074001, 2018.
Glenn M Fung and Olvi L Mangasarian. Multicategory proximal support vector machine classifiers. Machine Learning, (112):7779 2005.
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters, 100516))6 2008.
Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15): 2009.
S Sathiya Keerthi and Dennis DeCoste. A modified finite newton method for fast solution of large scale linear SVMs. Journal of Machine Learning Research, 6:341-361, 2005.
Shelby Kimmel, Cedric Yen-Yu Yu Lin, Guang Hao Low, Maris Ozols, and Theodore Yoder. Hamil- tonian simulation with optimal sample complexity. upj Quantum Information, 3(1):13, 2017.
Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for training linear and kernel-based classifiers. In Proceedings of the 36th International Conference on Ma- chine Learning, pp. 3815-3824, 2019.
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis.
Nature Physics, 10(9):631, 2014.
Stefano Melacci and Mikhail Belkin. Laplacian support vector machines trained in the primal.
Journal of Machine Learning Research, 12(Mar): 2011.
Alejandro Perdomo-Ortiz, Marcello Benedetti, John Realpe-Gómez, and Rupak Biswas. Oppor- tunities and challenges for quantum-assisted machine learning in near-term quantum computers. Quantum Science and Techmology, 3(3)003550,, 2018.
John Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. Technical Report SSR-TRR98-11 14, Microsoft, 1998.
Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 1 113(13):130503, 2014a.
Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 1 11((13) 2014b.
M. Schuld and F. Petruccione. Supervised Learning with Quantum Computers. Springer Nature, 2018.
Shai Shalev-Shwarzz, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: Primal estimated sub-gradient solver for svm Mathematical Programming, 127(1)33-30, 2011.
Johan AK Suykens and Joos Vandewalle. Least squares support vector machine classifiers. Neural Processing Letters, 93):2933-300 1999.


Reviews:
[{"review_id": "rJedR_MxqS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a quantum computer-based algorithm for semi-supervised least squared kernel SVM. This work builds upon LS-SVM of Rebentrost et al (2014b) which developed a quantum algorithm for the supervised version of the problem. While the main selling point of quantum LS-SVM is that it scales logarithmically with data size, supervised algorithms shall not fully enjoy logarithmic scaling unless the cost for collecting labeled data is also logarithmic, which is unlikely. Therefore, semi-supervised setting is certainly appealing. Technically, there are two main contributions. The first is the method of providing Laplacian as an input to the quantum computer. The second contribution, which is about the computation of matrix inverse (K + KLK)^{-1}, is a bit more technical, and could be considered as the main contribution of the paper.\n\nMy main concern about the paper is on its organization. The paper provides a very gentle introduction to both semi-supervised LS SVM and quantum LS-SVM. While this helps readers to be equipped with relevant background, it is at the cost of having less space for the main contribution in Section 3.2. I would suggest to remove the content in page 2; most results about kernel methods are not really relevant to this paper. For a machine learning conference paper, one shall safely start with half-page intro in page 3. Some background in quantum computing offered in page 3, 4, 5 are quite nice, but for a conference paper, I think this is an overkill. I recommend providing the very minimal content needed to discuss Section 3.2, and then use more space to discuss the idea in 3.2 better. Specifically, Generalized LMR technique and Hermitian polynomials in Kimmel et al. (2017) could be discussed in more detail. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxO2en0tH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to extend a quantum-computing based solution of least-squares support-vector-machine to include use of unlabeled samples.  The formulation is analogous to the classical-computing case, in which semi-supervised learning introduces an additional term in the system of equations, which the authors show how to compute in the quantum setting without degrading big-O complexity.\n\nI would lean toward rejecting this paper,  primarily on account of how the contribution relates to the publication venue.  The primary contribution lies in the procedure for preparing and propagating the quantum mechanical states needed to compute on the additional term.  Although the application is machine learning, the technique itself is still rather afar from this topic and would not appear to be of general benefit to conference-goers outside of quantum computing.  The overwhelming majority of quantum machine learning references in this paper appear in physics journals (all but one, which was ICML 2019).  Most of this paper is background material, which yet remains inadequate to convey insights into design decisions in the details of their main contribution, the derivations in section 3.2.  (I have a background in physics but not quantum computing.)   \n\nPerhaps a paper organization more amenable to this venue would be to shift some of the lengthier equations into an appendix and use the space of the paper to discuss a more conceptual and contextual understanding of why this technique is desirable, at each step, relative to other possible quantum techniques.  For example, Figure 1 is not explained, and is not decipherable to someone outside the field, so doesn't itself add to the story.\n\nCould be really good work, but the presentation doesn't quite come across.\n\n\nEDIT:  See comments to do with paper revision, which significantly improved the presentation.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJxnkesP5H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper developes a quantum algorithm for kernel-based support vector machine working in a semi-supervised learning setting. The motivation is to utilise the significant advantage of quantum computation to train machine learning models on large-scale datasets efficiently. This paper reviews the existing work on using quantum computing for least-squares svm (via solving quantum linear systems of equations) and then extends it to deal with kernel svm in a semi-supervised setting. \n\nStrengths: This is an interesting emerging research topic that has its significance. Also, this paper prodives a nice tutorial on the key ideas of quantum machine learning and provides detailed derivations and analysis on the proposed algorithm.\n\nWeaknesses: The novelty of this work seems to be incremental. It largely extends the existing algorithms such as HHL and LMR. \n\nMinor issues:\n\n1. Can any experimental study or applications be demonstrated, or only theoretical comptuational complexity can be compared? \n2. In Section 1.1, L is defined as L = G_I G^T_I. In this definition, whether and how the edge weights are considered? Please clarify.   ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers have assessed this paper and they have scored it 6/6/6 after rebuttal with one reviewer hesitating about the appropriateness of this submission to ML venues. The reviewers have raised a number of criticisms such as an incremental nature of the paper (HHL and LMR algorithms) and the main contributions lying more within the field of quantum computing than ML. The paper was discussed with reviewers, buddy AC and chairs. On balance, it was concluded that this paper is minimally below the acceptance threshold. We encourage authors to consider all criticism, improve the paper and resubmit to another venue as there is some merit to the proposed idea.

Decision: Reject