Quantum algorithm for finding the negative curvature direction
Authors: Kaining Zhang
Min-Hsiu Hsieh
Liu Liu
Dacheng Tao
Venue:  (2020)
Keywords: quantum algorithm
negative curvature

Abstract: We present an efficient quantum algorithm aiming to find the negative curvature direction for escaping the saddle point, which is a critical subroutine for many second-order non-convex optimization algorithms. We prove that our algorithm could produce the target state corresponding to the negative curvature direction with query complexity O(polylog(d)ε^(-1)), where d is the dimension of the optimization function. The quantum negative curvature finding algorithm is exponentially faster than any known classical method which takes time at least O(dε^(−1/2)). Moreover, we propose an efficient algorithm to achieve the classical read-out of the target state. Our classical read-out algorithm runs exponentially faster on the degree of d than existing counterparts.

Under review as a conference paper at ICLR 2020
QUANTUM ALGORITHM FOR FINDING THE NEGATIVE CURVATURE DIRECTION
Anonymous authors Paper under double-blind review
ABSTRACT
We present an efficient quantum algorithm aiming to find the negative curvature direction for escaping the saddle point, which is a critical subroutine for many second-order non-convex optimization algorithms. We prove that our algorithm could produce the target state corresponding to the negative curvature direction with query complexity (ppolylog(d) mization function. The quantum negative curvature finding algorithm is exponen- tially faster than any known classical method which takes time least O(de 1/2). Moreover, we propose an efficient algorithm to achieve the classical read-out of the target state. Our classical read-out algorithm runs exponentially faster on the degree of d than existing counterparts.
where d is the dimension of the opti-
INTRODUCTION
Algorithms for finding the minima of functions have attracted significant attention due in part to their prevalent applications in machine learning, deep learning and robust statistics; in particular, those with good complexity guarantees that can converge to the local minima. Numerous algorithms have been proposed in recent years for finding points that satisfying
/ (a:) I Eg. and Amin (V2 (V²((x)) (x)) --1
where Eg E (0, 1). Recent proposals (Nesterov & Polyak, 2006; Conn et al., 2000; Agarwal et al., 2017) based on second-order Newton-type and first-order methodology have been analyzed from such perspective. However, those methods normally deal with the situations that the iterations may be trapped in the saddle points, since in many cases, such as deep neural networks (Dauphin et al., 2014; Choromanska et al., 2015), existence of many saddle points is the main bottleneck.
In general non-convex optimization, many algorithms have been proposed escape the saddle points. These algorithms can be divided into the following two categories: the first-order gradient- based algorithms and the second-order Hessian-based algorithms. Generally, second-order algo- rithms have better iteration complexity than first-order algorithms (cf. Jin et al. (2017)). However, each iteration in the second-order method involves the computation of the negative curvature di- rection, namely, the eigenvector of Hessian matrix H V fxx) with negative eigenvalue. This computation could take time (dd) when the Hessian matrix is given, or O(d/ /c) when Lanezos method is used with Gradient information to approximate the Hessian-vecton product.
Quantum algorithms have shown great potential to become faster alternatives than classical algo- rithms for many kinds of problems in the field of linear algehra, including principal component analysis (Lloyd et al., 2014), support-vector machine (Rebentrost et al., 2014), singular value de- composition (Rebentrost al., 2018). These works encourage algorithm for finding the negative curvature. To begin with, we formally define the negative curva- ture finding problem as follows.
develop an efficient quantum
Negative Curvature Finding (NCF) problem: Given a function f(x) Rd + E. which has L- Lipschitz continuous gradient and the corresponding Hessian, we aim to build quantum algorithum that could efficiently provide the unit vector u with the condition:
n1 T Hu S +

---

Under review as a conference paper at ICLR 2020
where O < < L and
0 < c make the non-vector statement that with high probability there no unit vector u satisfying the following condition:
u Hu
1.1 RELATED WORK
Optimization methods for non-convex problems can be roughly divided into first-order and second- order methods, depending on the order of the derivative to the objective function they used. Gen- erally, the second-order methods (Carmon et al., 2018; Agarwal et al., 2017) are exploited to find the effective direction to escape the saddle point. Specifically, finding the Negative Curvature is considered critical subroutine analyze the characteristic of the saddle point.
First-order algorithms: For the non-convex problem, the first-order method (Gradient-bases method) find the stationary point, which could be global minima, local minima saddle point. However, standard analysis by gradient descent cannot distinguish between saddle points and local minima, leaving open the possibility that gradient descent may get stuck at saddle points. Re- cently Ge et al. (2015); Jin et al. (2017; 2019) showed that by adding noise at each step, gradient descent can escape all saddle points in polynomial number of iterations. Lee et al. (2016) proved that under similar conditions, gradient descent with random initialization avoids saddle points even without adding noise. However, each step of Gradient-ber baased methods requires (d) operations and their iteration complexity is higher than second-order algorithms (Jin et al., 2017).
Second-order algorithms:
Traditionally, second-order Newton- based methods can converge to lo- cal minima, which use the Hessian information to distinguish between first-order and second-order stationary points. There are two kinds of methods that make use of Hessian information. 1) Hessian- based: trust-region (Conn et al., 2000) and cubic regularization (Nesterov & Polyak, 2006) are two methods, in which the sub-problem is to find the decrease direction based on the given Hessian. The calculation of each iteration involves performing Hessian-vecte production, which takes time at least (d 2) Hessian- free: The Hessian-fres free methods use Lanczos method to calculate the negative curvature direction and use gradient to approximate the Hessian-vector product (Agarwal et al., 2017; Carmon et al., 2018; Carmon & Duchi, 2016). The Hessian-free method involves Ode 1/2) complexity per iteration. The advantage of the second-order algorithm is the superior iteration complexity than the first-order algorithm. However, using Hessian information usually increases computation time per iteration.
Quantum Algorithm for Linear Algebra: There are some proposed quantum algorithms for problems in the related linear algebra field. For example, given copies to quantum state p
Ei Zigli>(i,, where Iij is the j,j-th element of x matrix X with eigen- iigenddecomposition
x= Iran(((X Aunua previous quantum PCA algorithm (Lloyd et al., 2014) could perform the mapping E, 8)lu,) + E, S Xj) in time (ppolylog(d)e -3) However, the quantum PCA model use the density matrix to store the information of matrix X, which implicitly assumes the condition |
and Junin()) Another quantum SVD algorithm (Rebentrost al., 2018) shows an efficient method to estimate the value \// with error in time O(--3), for d x d matrix X with eigenvalues {A, 1 However, this model only suits the case when Ay is relatively large, and it would take time O(d to produce e-estimation works did not study the classical read-out of the output state, which generally takes time at least (d) for d-dimensional state (Aaronson, 2015), and could offset the claimed quantum speed-up.
eigenvalues. Moreover, both of these
1.2 OUR CONTRIBUTION
The contribution of this work can be briefly divided into two parts: 1) efficient quantum algorithm to generate the required quantum state, which corresponds to the negative curvature direction, and 2) efficient quantum algorithm obtain the description of the target state |u,) = - where { {
is an independent vector set selected from columns of Hessian H with rank r.
Negative Curvature Finding: We develop efficient quantum algorithm to produce the target state u.) (for case (1)) or make the non-vector statement (for case (2)). We provide Proposition the main result of this part, which guarantees the time complexity of our NCF algorithm:
2

---

Under review as a conference paper at ICLR 2020
There exists quantum algorithm which could solve the Negative Curvature Finding problem in time O1polylog())poly(r/b polpoyy()ee")), by providing the target state (we) (for case (1)), or making the non-vector statement (for case (2)).
Proposition 1.
Classical Read-out: The classical read-out problem one bottleneck for many quantum machine learning algorithms whose results are quantum states. Generally, the read-out of a d-dimensional quantum state takes time at least (dd) (Aaronson, 2015), and could offset the claimed quantum speed-up. In order to solve this dilemma, we develop an efficient quantum algorithm for the clas- sical read-out of the target state. We notice that the target state |u,) can be written as the linear combination form (2)) = i=1 Zz(ss),, where {s, a linearly independent basis sampled from column vectors (h, ) The algorithm suits the case when the result quantum state lies in the span of several given states, and may give rise to independent interest.
One advantage of generating the form U2) = = æs|s;)) ) is that it provides the target eigenvector as the linear-sum of r columns, which guides the curvature direction in general second-order methods. Our state read-out algorithm contains the State Overlap Estimation. The main results about the Complete Basis Selection and the Classical Read-out are briefly summarized as following theorems:
subroutines named the Complete Basis Selection and
Theorem 1, There exists a quantum algorithm which takes time ((poly(r))-2p9) to find an index set {g(i))= where r is the rank of H. log Arl HilE and {g( forms complete basis ((g(t) ) F.=1 with probability at least 3/4.
Theorem 2. The classical description of the target state (u,) = Ei=ia could be presented in time ((polylog(()ooly()))) 5) with error bounds in 5, when the basis set {s,}/=1 is given.
The rest of this paper is organized follows. Some preliminaries about quantum information introduced Section 2. In Section 3, we develop an quantum algorithm to solve the NCF prob- lem. In Section 4, we develop an quantum algorithm which aims read the target state. We summarize our results and contributions in Section 5.
2
PRELIMINARY
In this section we present some preliminary concepts. Some basic quantum knowledge will be introduced in Section 2.1. Some quantum technics will be introduced in Section 2.2.
2.1 NOTATIONS AND DEFINITIONS
In this section, we introduce some useful notations and definitions about quantum computing. The dirac notation is standard notation in quantum mechanies describe the quantum states. The form (æ) is the state which corresponds to the vector æ, and the form (y)l is the state which corresponds to the vector y" The notation (y)az) denotes the value y "xx((( [1] y [=]]= The notation
ly) (ax) denotes
the matrix yæ: /([lv/|||==]) Quantum state is unitary, which means |||=:)|2 (m|=) = 1. Thus
for vector æ Rdd the state (a)) is defined Σ / ||==]]];] where x; is the j-th component of vector æ and {1i) } is the state basis which acts like {eg}d=1 in classical case. One could obtain information from the quantum state by performing measurement. For example, the measurement of (z) on the basis {b)) 15=1 could randomly produce different index with probability 2//1
We use [n] to denote the set {1, (1,2,...,,4 and the spectral norm for matrix, if there is no more explanation. |||] = -E
We denote the norm || || as the | norm for vector
- 1/22 is the Frobenius norm of matrix A E _u The lowercase form h; is defined as the i-th column vector of matrix H pdxd I; is defined as the i-th component of vector æ. The tensor product of two matrix A Rmxn and B E RPx0 is defined could be performed between vectors, since vector is one special kind of matrix. The tensor product could be defined between quantum states |æ:) and (222) which is written as (x)) (22). We present definitions of smoothness and 7-separation here.
C = A & B. The tensor product operation
Definition 1. (smoothnesss) A function f Rd + R is L-smooth if it has L-Lipschitz contimuous gradient, that is [[V V)(y)) T.|xx yll. Var, y E X, where X is the domain of J (x)).
3

---

Under review as a conference paper at ICLR 2020
Definition 2. (y-separation) The set G {[1, "2,-. .On) is said be y-separated if aa ag) Y, Vi, E [m] and i + j.
Based on these definitions, we assume that the Hessian H in this article has two properties:
1. Hessian H Rdxd a r-rank matrix;
2. The absolute value H's non-zero eigenvalue is e-separated.
The first property is directly derived from the assumption previous classical non-convex opti- mization method (Carmon al., 2018), and the low-rank Hessian case has been observed in neural networks (Gur-Ari et al., 2018). The second property is assumed such that we could distinguish different eigenvalues by their absolute value. We further assume that the Hessian matrix H has the eigen-decomposition H = ン== 2ou52,z for the convenience of following discussion.
2.2 TECHNIQUES
The motivation idea behind our approach is to perform the quantum singular value estimation model and then generate eigen-states by the post-selection on the output state. Here we introduce two techniques including oracle models and critical conclusions in previous work.
Quantum Oracle Models (Kerenidis & Prakash, 2016): For the whole paper, we assume the ex- istence of following quantum oracles, and discuss the query complexity of our algorithms these oracles. Given Hessian H E Rddd, we assume that H is stored in classical data structure such that the following quantum oracles could implemented:
Un 10]10) + 11)),))
b111))1), Vi [d].
(3)
h2
d
Vn (0)l)) - (h)1))
hall [d],
(4)
H
where h stands for the d-dimensional vector whose i-th component is ||/:|||||
The required data structure has binary tree form. The sign and square value for each entry stored in different leaves and the value stored in each parent node is the sum of its children's value. A detail description about this data structure can be referred to (Kerenidis & Prakash, 2016). Denote T' as the time complexity of these oracles.
Quantum Singular Value Estimation (SVE): Given matrix H Igdd which has the eigenvalue decomposition H = E/=1 X, previous work (Kerenidis & Prakash, 2016) provided quan- tum SVE algorithm, which could be used for estimating singular value or generating eigenstate. Here we briefly introduce their conclusion about the time complexity of their algorithm:
Theorem 3. (Kerenidis Prakash, 2016) Suppose quantum accesses to oracles (3) and (4) exist. There is an algorithm which could perform the mapping E; ()) + Σ3 By (,lb))ll>y)) with time complexity 1 1-1 (d)/polydd).
where RS E 1A, - -e|| X, +e|l
H| +e||H[]
with probability least
QUANTUM NEGATIVE CURVATURE FINDING ALGORITHM
Our main contribution in this section is the quantum Negative Curvature Finding (quantum NCF)
algorithm presented in Algorithm 1. The quantum NCF algorithm solves the NCF problem by providing the target state (u.) (for case (I)) or making the non-vector statement (for case (2)). The target state (u)) corresponds to the eigenvector u, which satisfies the condition vi Hu, < t/22 Here we present a tighter restrict on the target state u4)) to keep a c/2 redundancy for the classical read-out of the quantum state. The quantum NCF Algorithm uses the Proper Eigenvalue Labelling (Algorithm 2) and the Target State Generating Algorithm (Algorithm in Appendix) as subroutines proposed in Section 3.2 and Section 3.3, respectively.
4

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Quantum Negative Curvature Finding (Quantum NCF) Algorithm
Input:
Quantum access to oracles UH and VH. The parameter e and a in the NCF problem. The target state (ug) whose corrsponding classical unit vector un satisfies the condition
Output:
u Hu, -a c/2; or a statement with high probability that there is no such kind of unit vector u which satisfies the condition u² Hu I -a.
1: Label the proper(less than -a + e/2) eigenvalue of H (Proper Eigenvalue Labelling).
2: if the least eigenvalue of H is less than -a + c/2. then
3: generate the target state (Target State Generating Algorithm) and output the state;
4: else.
5:
claim that there is no such kind of unit vector u which satisfies the condition u" "Hu S -a.
6: end if
3.1 CHALLENGES TO DEVELOP QUANTUM NCF ALGORITHM
The core technical component of our quantum algorithm for the NCF problem is the quantum SVE algorithm. However, there are three major challenges that we have to overcome.
Firstly, the positive-negative eigenvalue problem. In the negative curvature finding problem, we are interested in obtaining cigenvectors with negative eigenvalues. Hence, we cannot directly apply the quantum SVE algorithm since it only gives the estimation on |Ayl- In order to overcome this critical issue, we develop Algorithm 4 in Appendix label negative eigenvalues.
Secondly, since the quantum SVE Algorithm presents e-estimation on singular values with time complexity 1 | ||| ppolyllog(( ) 3), we need to provide tight upper bound for the Frobenius norm HH| H|,, which is shown in Lemma 1:
Lemma Suppose H E Raddd is the Hessian matrix derived from the function J Rd TR which has the I--Lipschitz continuous gradient. Thus the Frobenius norm of H has the upper bound | | S VTL, where r is the rank of H.
Finally, the input-state problem. For the general superposition state Ezdgluy), the output state of quantum SVE algorithm has the form E, 11 We could generate different pure state |uy) with probability | by the measurement on eigenvalue register. Thus in order to guarantee a small time complexity, need to prepare special input state such that the overlap between the input and the target state is relatively large. We briefly summarize our conclusion on the time complexity of Algorithm in Proposition 2.
|| polyyolylog(d)= to solve the negative curvature finding problem by providing the target state (u,) or making the statement that there is no unit vector satisfies the condition u² hHH
Proposition 2. Algorithm/ I takes time O(T H
Hu < -a.
3.2 POSITIVE-NEGATIV EIGENVALUE DISCRIMINATION
In this section, we propose an algorithm aiming to label the target eigenvalue which is less than -a+ e/2. This algorithm helps verifying the existence of solution to the NCF problem and generating the target state. Since the eigenvalue information of H is unknown to us, we need to build the Algorithm label the proper eigenvalue, which would benefit the target state generation task in the following section. The proper eigenvalue means the eigenvalue is less than aa c/2. We view this kind of eigenvalue as our target eigenvalue.
The mean idea of Algorithm 2 is to use the input state
1 THE Ej=1 Ayluz)luy) for the quantum SVE
model and obtain the state:
|
The measurement the eigenvalue register would lead this entangled state collapse to different states ()))) for j E [r]. We could obtain the state |uy) by neglecting the state in any other register. Using state /u,) to apply the PNED algorithm (Algorithm 4 in appendix) could provide a discrimination on the positive and negative of the corresponding eigenvalue Ay. Thus, we could label the proper eigenvalue, for the that the least eigenvalue less than -a+e/22 make the
5

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Proper Eigenvalue Labelling
Input: Quantum access to oracles UH and Vи. The parameter e and a in the NCF problem. Output: A proper label to the singularvalue |Ayl such that X5 S a + e/2 with probability - 6, or a non-vector statement that there is no unit vector u which satisfies u² Hu < -a. 4|| a (2 - log 8 + 3) do
1: for k to
2:
Create the state | Σj m uy)-
3:
Apply the quantum SVE model obtain the state 1 || Σj A5 (ل))) where
[Agl E |Ayl = c/4 with probability 1/poly(d).
4:
Measure the eigenvalue register and mark the result.
5: Use the rest state in the first register as the input apply the PNED algorithm.
6: end for
7: Count the result in step and step obtain the sequence {(Ayy], ny my) ny is the number
of resulting |Ayl in step 4, and m, is the number of resulting 1 in step 5 for different lAyl-
8: if my
ny <2 for all j E [r). then make the non-vector statement;
9: else, choose the largest 1ス5l which satisfies the condition My
10: if | < e/4, then make the no-vector statement;
11: else, label eigenvalue X as the proper eigenvalue.
12: end if
13: end if
non-vector statement, for the case that all of eigenvalues are greater than -a. We present the time complexity of Algorithm in Theorem
Theorem 4. Algorithm could label the proper eigenvalue of H with probability 1 1/poly (d), or claim with high probability that there is no unit vector u which satisfies u² Hu < -a, with time complexity (THH H || polylog(d))) -1))
3.3 TARGET STATE GENERATING
Suppose the result of Algorithm implies the existence of the target eigenvector uy which satisfies u, Hu:
c/2. Then in order to give solution to the NCF problem, need obtain the vector u, In this section we construct a quantum procedure to generate the state /ur). The classical read-out of |u), which means estimate vector u, from quantum state ue)), will be discussed in the following section. The idea is very similar to Algorithm 2. We still use state |H| Σラ=1 \u)
as the input of quantum SVE algorithm to obtain state:
X
H
Suppose >e denotes the eigenvalue of (u.) that A, S -e The measurement on the eigenvalue
register could generate state |u:)| with probability Pt
X²
म. Thus the probability
a²
H log
of generating least one state (u:) in N
times of measurement is 1
- (1) There is: - (1 - P.) 2 1 - N > 1 1-c log(1/6) = - 8. So state lur) could be generated in N times of measurement with probability least 1 - 8. By considering the time complexity to run the quantum SVE algorithm (O(TH H| pdlylog(d)e
and setting the could derive the time complexity of generating target state in Theorem 5. The detail of Target State Generating algorithm is in Appendix (Algorithm 5).
probability error bound 8 = 1/))
Theorem 5. Suppose that Hessian H has the eigenvector u, with eigenvalue less than -a + 5. Then state ju.) could be generated in time (T H | polyloly with probability at least 1 1/poly(d).

---

Under review as a conference paper at ICLR 2020
4 STATE READ-OUT
In this section, we propose an efficient algorithm to read-out the classical vector u4 from the quantum state (u,). Generally, the classical read-out of a d-dimensional quantum state takes at least (dd) times of measurement to obtain the form |a:) = > Z.C., Thus the classical read-out of the required state could offset the exponential speed-up (Aaronson, 2015) provided in many quantum machine learning algorithms. In order to avoid this problem, propose quantum-classical hybrid procedure to rewrite the target state (u)) as the linear combination of states, which is selected from column vectors of Hessian H. The main result is stated in Proposition 3.
Proposition 3. The classical description of the target state la,)) Ei=1 za (g())) could be pre- sented in time (T poly((())) with error bounds in e/2, when the complete basis set { Vj=1 is given.
Recall that our Hessian matrix H Rdxd has the eigendecomposition H Σj= uz where A is the eigenvalue of И with respect to eigenvector uj. Then, any eigenvector of H that cor- responds to a non-zero cigenvalue could be represented as the linear combination of vectors in {h,] because Huj- Λyu; can be written as Σi= h:u, AyUj. Since H has the rank of there exists subset of complete basis {hg()) J of the column space, which is sampled from the set (hz) 1d Thus, any eigenvector u, could also be represented as the linear combination of vectors in (hg(()))=1
uz
Back to the state read-out problem, denote 8; as hg(s)) for simplicity. Suppose the target state (u,) that generated in the previous section can be written (us) = Σi= 24/s:), where {x;)]= are coordinates of the state (u,) under the basis {[x))= Thus, instead of simply reading out components of vector uy could get the classical description of |ıx)) by calculating each x;. Note that the complete basis {I ((,)) Yi is not unique and we only need to identify one of them.
We also notice some recent breakthrough, about quantum- -inntttrum-- algorithms (Tang, 2019; Arrazola et al., 2019), which are based on sampling technics and FKV Algorithm (Frieze et al., 2004). These quantum-inspired algorithms could perform approximate SVD which also outputs eigenvector the linear-sun sum on a group of column vectors. However, in order to cover the whole column space, the quantum-inspiree algorithm need to sample least 0 2 number of columns basis, while our method generate the linear-sum form exactly on r columns.
4.1 COMPLETE BASIS SELECTION
In this section, we develop quantum algorithm select a subset S -
.g(r) from
[d]. which corresponds to the complete basis { {))(() \ The quantum complete basis selection algorithm can be viewed as the quantum version of -raam-Shmidtt orthogonalization: firstly we choose [t1) (hg(1)) from the set (1h,) ) then given state set {[(m) M we choose [fz-1) x
(1)(+))) - Σ'_= [km) (2g(+1)> from the state set (1h,) - -' (cm) (fm |b1) Since the chosen| ((++) is orthogonal to states {/tm.) y for each iteration ( E [r-1], 1]. the state set {[tm) )r forms an orthonormal basis. Note that the state [t..) is generated along with an index g(m) for m [r),
would obtain complete basis index set {g(m) after the implementation of this quantum algorithm. The quantum complete basis selection algorithm is provided Algorithm 3, in which we denote:
(
Σ
I11bi
(2y)
Σ YOL
(tm (t 1 h
Σ vmml
tm)) (tm (tmmm/)//)).....
(5)
H
as the initial state in each iteration. The time complexity of Algorithm 3 is analyzed in Theorem 6. The detail about Algorithm 3 is in Appendix. We also provide Lemma 2 which provides the time complexity of confirming whether a given set { are linearly independent.
[[))))))) Theorem 6. The Algorithm takes time O(Tnpoly(r)e 2og(rr [[ w/e)) to find an index set
{o()) which forms a complete basis [ (h H with probability at least 3/4.
"(()) is the index of the i-th column vector in the complete basis.

---

Under review as a conference paper at ICLR 2020
Algorithm 3 Complete Basis Selection
Input: Quantum access to oracle UH and Vи.
Output:
The index set of the complete basis: S = {
Initialize the index set Ss
2: for I = 0 to 1 do
3:
Create the state ) defined in Equation (5).
4: Measure the third register of state (o(") multiple times to get the state _ which is pro-
portional THi Σj-n (d) || [hn)) - [km) (4m hng
5: Measure the first register and record the result g(t + 1).
6: Denote (144)) as the state proportional to (1g(1+1)) - Em= (m (bm (e
7: Update the index set S, U {g(l 1)}.
8:
end for
Lemma 2. takes (vr)) time to check whether the vector set {8,) is linearly independent when the classical access to Hessian H is given, where is sampled from column vectors of matrix H.
4.2 COORDINATES ESTIMATION
Assume the complete basis {[s1), (82), ... ...,,,,)) has been selected out in Section 4.1. Thus the read-out problem could be viewed as solving the equation lu,) = Ei=1 3y [&)), where 2; E R are unknown variables. The coordinate {x,),-, could be obtained by solving the r-dimensional linear equation system Cz = b, where b; = (u))s; and Cij = (s{(s)) f, E [r]. The equation C could be solved classically in at most (rr)) time. Note that we can only get the approximation to Cij 6; instead of the exact value. Theorem verifies the impact of the approximate error to cij or b, on the read-out of the target state.
Theorem 7, Suppose Cjk is the e E--apprxximatin to Cjk = (s, 5x) and by is the ea-approximation to bj- = (u]]s)), Vj. k E [r), where 61 ---حC--र and 62 ल-ाल---. Denote vector R2" the solution of Car b. Then in could lead an approximate eigenvector | url S e/2.
Ej=1 3z885 such that
We propose several methods in Appendix to estimate overlap by = (utls:) and Cj = (s which are based on the Quantum SWAP Test (Buhrman al., 2001) and the Hadamard Test. Our proposed quantum algorithms could present esstimaation to Cij = (8i(s,) in time OTT 2 and ez-estimation to b, (ur)s,) in time ((TTmppu + TT) where Traput is the time to generate state (u)). Since the time complexity to generate the target state is OTH H polylog (d) as proposed in Theorem 5, we could derive Proposition 3.
Considering the time complexity O(TH || polylogg(d)) to label the proper eigenvalue and to generate the complete basis set, we could by providing
the time complexity (e 2,.2 solve the NCF problem in time O (ogpolyyog(()poly( the target vector in the form u, Σi= r.h ht)) hg)l with error bounded by or making the non-vector statement.
+ l0
CONCLUSION
We propose an efficient quantum algorithm for the Negative Curvature Finding problem, which is critical subroutine in many second-order methods for non-convex optimization. The proposed quantum algorithm could produce the target state in time O(T ( (ooy--ooolylorllllll (dlylog(d)) with prob- ability 1/poly(d), which runs exponentially faster than existing classical methods. Moreover, we propose an efficient hybrid quantum-classical algorithm for the efficient classical read-out of the target state with time complexity (T pollyll)
polylog(d))) (d)e 2 (( + ? log(4r H| / which is exponentially faster the degree of d than existing general quantum state read-out methods.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Scott Aaronson. Quantum machine learning algorithms: Read the fine print. 2015.
Naman Agarwal, Zeyuan Allen- Zhu,, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approxi- mate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199. ACM, 2017.
Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. Quantum-inspired algorithms in practice. arXiv preprint arXiv:1905.10413 2019.
Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum fingerprinting. Phys- ical Review Letters, (7(16) 2001.
Yair Carmon and John C Duchi. Gradient descent efficiently finds the cubic-regularized non-convex newton step. arXiv preprint arXiv: 2016.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2):155-11772, 2018.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pp. 192-204, 2015.
Andrew R Conn, Nicholas IM Gould, and Ph L Toint. Trust region methods, volume 1. Siam, 2000.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex op- timization. In Advances neural information processing systems, pp. 2933-2941, 2014.
Alan Frieze, Ravi Kannan, and Santosh Vempala. Fast monte-carlo algorithms for finding low-rank approximations. J. ACM, 5166):1025-004,, November 2004. ISSN 0004-5411. doi: 10.1 1039488.1039494 URL http: /toii acm. org/10..///0 111111111199/ 1039494.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle pointsonline stochastic gradient for tensor decomposition. In Conference on Learning Theory, pp. 797-842, 2015.
Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace. arXiv preprint arXiv:1812.20 18/2.04754 2018
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pp. 409-4264 Springer, 1994.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1724-1732. JMLR. org, 2017.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan, Stochastic gradient descent escapes saddle points efficiently. arXiv preprint arXiv:1902.0444 1902.0481,, 2019.
Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. arXiv preprint arXiv:1603.0867,, 2016.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference learning theory, pp. 1246-1257, 2016.
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis.
Nature Physics, 10(9)6631, 2014.
Yurii Nesterov and Boris T Polyak. Cubic regularization newton method and its global perfor-
mance. Mathematcaal Programming. 108(1):177-205, 2006.
Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical review letters, 11 113(13):130003 2014.
Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd. Quantum singular-valus de- composition of nonsparse low-rank matrices. Physical review A, (3322 2018.

---

Under review as a conference paper at ICLR 2020
Alex Schwarzenberg- -zemyy. On matrix factorization and efficient least squares solution. Astronomy and Astrophysics Supplement Series, 110:405, 1995.
Changpeng Shao. From linear combination of quantum states to grover's searching algorithm. arXiv preprint 1807 00000,9 2018.
Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Anmual ACM SIGACT Symposium on Theory of Computing, pp. 217-228. ACM, 2019.
A APPENDIX
A.1 THE PROOF OF THEOREM
Proof. The time complexity of Algorithm could be directly obtained by the time complexity of
Algorithm and Algorithm 5, whose complexity analysis are presented in Theorem 4 and Theorem respectively.
A.2 THE PROOF OF LEMMA Proof.
Assume \ S X2 S
S As are eigenvalues H, we have:
min v" HU H max ve HU, Vj E [d]
|
By the definition of the Hessian matrix, for unit vector we have:
Vf(x + hw) - vf(x)
He f(z)v= lim
h
From above equation, we can obtain:
2 TH < ||||| HHl| & lim (VV( < 1im; h
L[livell L,
and v0 Hu - |0|| Hel m|| 2 lim [ ((lnthh)-VViaa vs()]l lim Likell -L.
Thus, the eigenvalue Xy is bounded in [-L, L] for all j E [d].
| S VTl. We have H Σ, M2 = Tr(H (H. H) E, X H SrT? so
Lemma 3. Hoeffding's inequality (Hoelfding, 1994)
Suppose X2, .n, are independent random variables with bounds X; E [ai, bi], Vi E [n].
Define X = Em= Xz, then Ve >> O, we have:
2n
P(X F 2 5 eexp
(6)
Σ (b, a,
and
2n²
P(X - - < -E)
exp
Σ (b. a1,
A.3 THE DETAIL ABOUT ALGORITIM 4
In Algorithm P E oe xd is the matrix whose column vector p; C; ? hi for [d] and hhlll
Q E Rdd xd is the matrix whose column vector | & e, for j E [d]. h; is the i-th column vector matrix H and h is d d-dimensional vector whose i-th component is [hall It can be directly obtained that the matrix P and satisfy the decomposition H H || PP Q and have property p'P = QºQ = I. Mappings |x) [0) + PPx) and (z) + IQx) can be performed by the quantum oracle Un and Vμ respectively.
10

---

Under review as a conference paper at ICLR 2020
Algorithm 4 Positive-Negatic Eigenvalue Discriminatioo(PNEDD) Algorithm
Input: Quantum access to oracles UH and Vи. Eigenstate u) which corresponds to eigenvalue
Output: A random boolean variable with distribution P(0) 1+ and P(1) = 1- Ir.
1: Create state (4) [0] (0).
2: Apply the Hadmard gate on the third register to obtain the state /2 (1u) (0) (0) + ())0))1))
3: Apply the Controlled-SWAP gate to obtain the state J (1x4 [0] + (0) 1))-
4: Apply gate Uи @ [0)(0] + VH @ [1] (1) on the state to obtain v/2 Pu) |0] IQu) 1))
5: Apply the Hadmard gate on the third register to obtain the state P + Qui
(0) [Pu) Qui
1).
2
6: Measure the third register and output the result.
Theorem 8. Positive-negative eigenvalue discrimination. For eigenvalue À of H with property
[X] 2 one could Algorithm 4 for
[ 2 log 1 8 2 |
2] + 3 times, to make statement that
is positive or negative, with probability 1 6.
Proof. The measurement in step 6 of Algorithm 4 outputs with probability:
Pu)
Qu)
1 1| 4 ((Pu) (Qul)((P)) - -QQu)).
P(1)
Note that (Pu Qu)
TH DT Qu
u Hu
| so P(1)
1-
-iiillrrly we
2
have P(0) H|l
Suppose that need 2x +1 times of measurement give an 1 8 correct statement about whether > 0 or X < 0. The problem can be viewed as the biased coin problem. Define random variables
X; such that P(X; 1) - p and P(X; 0) 1 p and S,, Σi= X;. Then there has the
Hoeffding's 's inequality P(S,/n
I - S e 2ne² and P(Sn/ n p 2 c) I 2mm??
Back to the problem, suppose X < 0, by setting 2x + 1, n(p we have:
and P 1- HIE
P(S2++1 2z) exp(-2(22 1)[ X/H
12
2n+1
7 <
1
2x
22 1
Similarly for A 0, there P(S2441 2 2x
20t1 I
Let
< 6, we have x 2 ||
1 log
+
5
2
A.4 THE PROOF OF THEOREM
Proof.
The input state
1
Ej >₂ )zlu;)lus) could be generated with oracles Un and VH:
THI
10)
VR
hhel h
UR
h 1))
(9)
H
|
Since H has the dicon-decomposiiton H = Ei=1 Auuaef we could rewrite entry hig as (6) (6)
hij = Ei dxu uk where us is the i-th component of vector uk- Thus the state
H Σd Ei=1 Ei EØ=1 by (8)1)) could be written as:
d
Aaa
(9 (0D) u
Σ
du )ulle)) (24))-
|
j=n
Then apply the quantum SVE model on this state. In order give e/ e/4-estimation the singular value, the time complexity to run the quantum SVE algorithm OT ir pollllllgg by Theorem 3.
11

---

Under review as a conference paper at ICLR 2020
Suppose there eigenvalues Ay which are less than -a + c/2. We denote the least X and
label it the proper eigenvalue. By Theorem 8, we need to generate - 2 | 2 log 8 1 +
x 6. Note that the
numbers of state (u,) in order to guarantee that X < with probability
x²
probability of generating state (ue) in each iteration of step 2-4 in Algorithm Hill
Hill Pt
So averagely we need to perform step 2-4 in Algorithm 2 for
[2]
log 1 1 +3
x
A
times. The number can be roughly upper bounded by 4
a² log # +3), since for negative (2 [1 a²
curvature case < a, we have Ael a c/2 > a/2.
By considering the time complexity to (O || | polyloogdd))))) and setting the probability enror bound 5 = 1/poly(d), we could derive that the time complexity of Algorithm 2 is O(Tn H polylogggg()))
the quantum SVE algorithm
A.5 TARGET STATE GENERATING ALGORITHM
Algorithm Target State Generating
Input: Quantum access to oracles UH and VH. Parameters and e in the NCF problem. Output: The target state (ue) with property (u, (ul())())) = d S -a e/2.
F log } do
for k 1 to
a²
2: Create the state
T Σ Ag uy).
3: Apply the quantum SVE model to obtain the state | ES= Arl2y)(uyy)
where
| E |Аyl + e/4 with probability 11/1pllppppppp 1/poly(d).
4: Measure the eigenvalue register and mark the result.
5: if' the eigenvalue measured in step is labelled to be proper in Algorithm 2, then
6: output the state in the first register the target state.
7: end
8: end for
A.6 THE DETAIL ABOUT ALGORITHM 3
Consider the state:
I (
2 {) H
Ii (o)))
Σ
| l1bb)
{
[[n
Σ
|m (tm n2y)) 10) - Σ
It.) (tm 11y)11333 }
=
m=m
m=1
(10)
12

---

Under review as a conference paper at ICLR 2020
note that the state
)
in Step 3 of Algorithm 3 can be generated by the following procedure:
(a()))
10]10)
(a)
1
lo()))
h [1,))1))))
(11)
H
|
1
[0] + (1)
Lo())
Σ
(12)
||
V22
(0)
(9()))
d Σ
|
(1ag) - 2 Σ
mm (tm 12y)
10)
+
[1]
H
V22
v2
m=1
(13)
(d)
lo()))
m=1 {(te)
Σ
Im (ne (hi)) 11)
Σ
km
(fom 11
H
-=1
m==1
(14)
{[n))
(c)
Σ
[nn)
Σ m=1
[tm) (tu) (tmmlt()))) (hy) 10) Σ m=1
(m)) (tm
(
H
(15)
In step (a), we employ the quantum oracles UH VH on ancillas [0)]0]. In step (b), an auxiliary register (0) is appended, followed by a Hadamard gate. In step (c), we apply operation IT [Rm RRm
@
[0)(0) + & [1] The operation R., is defined on the register lg(1)), lg(m)), Ihz):
Rm = (m)+)) + 1) 2
{[[
(o(i))
[tm)
HI
[ (tm
==1
f=1
In step (d), we apply the Hadamard gate on the auxiliary register. In step (e), we trace out registers I'' (o))) generate state (o(").
The crucial part in Algorithm 3 is to implement the reflection Rm For the m 1 case, there is:
[mm+1) Zm--
(18m+1)
Σ (4 (t))(t(mm+1)))
(16)
Note that ([ forms the orthogonal basis: (tz(er) = O, Vi + j. and 7m+1 (fm+118mm1l)
||| [1m++)) E (4) s = /1 Ex (4: (m/mm++1
Denote (6,) = Σ j- m m5)18,). The restriction that (6m+1) is normalized and orthogonal to states
| (mmmm))))))))) could yield Equation (17):
Σ
3 Am ( 0, Vj [m].
(17)
m m+1
1.
Note that Tm+11m41 = 1/Zm+1 by Equation (16). Define the m-dimensional vectors x, b, and the m matrix O. to be:
m
m
Im Um+1lee b Σ 8)+1)ee Cm {cs = (s:1 mm.
where each value Cgg = (8))))) could be estimated by Hadamard Test. Thus, we could derive the following linear equations about æ from Equation (17):
Cm
b.
Zm+11
(18)
72
T b
Zm+1
13

---

Under review as a conference paper at ICLR 2020
We could obtain the coordinate {fm+1.) !
by solving Equation (18). There is:
Cm Cm+1l
1m+11m1
Zm+1
(19)
Im+1a
Vi
[m].
Zm++1
Cml
where matrix C denotes the matrix generated from Cm by replacing the i-th column with b. Suppose now we have obtained the linear combination form (tm+1) = m=+ Im+1,alst). Thus, we could construct a unitary to generate the state [ (g(و)) [tm+1) from the state [1 (0), by the iinear-ommiination-fff-oc
method (Shao, 2018).
The idea of linear combination of states was introduced in Shao (2018), which focuses on the fol- lowing problem: given quantum states (a} and 16). to prepare the state c)) = % (x|aa + v/6)). The method is based on the fact that R22 = (I 2/6) (b))(T (al) can be viewed the clockwise rotation in the plane spanned by |a) and (b) with angle 20, where = arccos(alD) is the angle between la) and [b). Thus any clockwise rotation in space SPAN (Ia), [b)] with angle ø could be written as Rs = R2/200 For the case lc) = Z (x/aa + y(b)), there is le) Røla), where arecos x+y(a/b) Ze
arccos V + +20y(abb) The linear sum of 2 states could be generalized to
x+y(ald)
case:
Theorem 9. (Shao, 2018) Assume state (ox) could be prepared by given unitary operation in time Tin for i E [n]. Then there is unitary which could prepure the state (e) Σi=1 04 agldss) time ( log(//e))) with error c.
Note that here we actually perform the state (2 la(1)) ... Ig(m + 4m) from states (lg())))(())) (g(m + 1)){s;) Het1, and each state (I (9(i)))ss;) could be performed by oracle UH on state ([1}=1 (e()))))0). Denote Un+1 as the unitary which generates the state | lg())) (m++)) from the state [I, 1s())
[0). The operation in step (c) of procedure (11): I [Rm @ 10)(0| + @ [1)(1] could be performed by I [ ( 200) @ [0)(0] - @ (1)
A.7 THE PROOF OF THEOREM
Denote P7 the probability of resulting 0 after the measurement in Step of Algorithm 3. In order to generate the required state, the measurement in Step 4 needs to be performed for (1/Pi) times. The Lemma provides lower bound on P..
Lemma 4. The probability of resulting after the measurement in Step 4 of Algorithm as the (y-1)²²
lower bound Pt 2 -11
Proof. Suppose X² 2 23 ... X2 where x; is the eigenvalue of H. Since state (tm.) is the linear
sum of (1h assume that [tm) has the decomposition (t...) Σ/= Wind (u;). for all
14

---

X? Under review as a conference paper at ICLR 2020
1,2, .1, where Ei=1 Wms
Wid Wi
8mn- There is:
Pr
|
Im (4m |esi ?1?
H
2 F
m=
||bb|12
Σ
| ( |ny3)
H
2
d
Σ
W A Ac (1)
И
jml m
1
Σ wh X (1 + Σ
Wme d4 (1) us
P
m=1
1
Wmss A
H
1=1
where C -
mm
Consider the r-dimensional vector Wm Ei= Wmse, The vector set {wm 2 forms an orthogonal basis in a I-dimensional subspace. Note that we can add Wi+1, w. such that (wm m= forms an orthonormal basis in the whole r-dimensional space. Denote matrix W (wi, ",,""', Wr). Since WTW = Since W is unitary, there is:
w = 1, [r]-
(20)
m==1
Thus we have the upper bound:
C Σ m=
Σn m=1 w2
1. Note that Σ C4
Ei whnt = -''
Ei= w = 1, there is:
P:
(21)
H
H F
Note that for the case [Asl < e/2, A, = 0 is a good estimation for the NCF problem, so we could
further assume Aul > c/2 for the general case and bound the inequality (21) as Pt 2 |||
(r-D)²
The error of implementing (bm+1) comes from the imperfect implementing of the linear- combination-oo-sstttee operation and the error of caleulating The former has been analyzed in Theorem 9. The error of calculating æ is more complex.
Define vector y = -2m+1æ. Note that all parameters Gy = {s.(ss), E [m]] and by (8m+1ls;).j E [m] are estimated by Hadamard test, which takes time ((T with error bounded in (see Appendix A.10 for more information). Thus the calculation on vector y C, b would have error. Define matrix Č. = C.. + AC,.. and i = b + Ab which are estimations on Cm and b. Suppose |ā. ciyl S él and |b; - byl < E are error bounds for Cjj and b, respectively, Vi,j E [m]. Denote ÿ = Ō b as the solution to the approximate linear equation and Ay = ÿ as the error to y. We have:
Cny =b. b. (Cm + (0 + An) = (b + Ab).
15

---

Under review as a conference paper at ICLR 2020
So there is:
| |I(Cm AmCm) ACm Cm
[ 1.(1II + +0 Am (| + + Cmlbl]
1
[0mll
(| + | [|]b[]]
1 ||Cmllac.
||m=]]
3/2
1 Cm [|me1 (Vmer + 3/2 e1 e | <
m
C ||me
The norm ||Cmll || here denotes the largest norm of eigenvalues of matrix C. Thus, for 62 = 3m 3/3 3/2 m [12 61, we have bound | S 62.
For [mm+1) = Ei=t Tm+1,1 83) and [8m+1) Eisr m+1
T Im+1,1 18)) there is:
m++ 1 m+1
m,m
m
1mm+1/mm-1) = Σ
Tm+ 1m++1,Ci5m+11. = Zm+ Zm41 im15=1
Σ
Σ
yib:
وزūو +
+1
j=1
j=1
[1 Σ
Bibyl
Zm+1 Zm+1
7m 7m++1
1=1
Note that the form
(lm+t) Dmet 1m+11i(8ss) is not normalized state:
11
Σ I C,g
Σ
+1 2 Σ 3/
72
m++1
(=1,==1
i=1
m.
y;Ciy + 2 m
Ay.b: 2 m
Ay;oAAy +2
Ays
Σ
> yob,
72
m++1
i=1Ø==
1=1f=
i111=1
m.m
22
m+11
+
Ayiay Ayjl
i=1-=1
Thus, the overlap between state (m+1) and (m++)) is:
(m+1)
Zm+1
(22)
Zaiti Ay" DyTCCAA Ay
There is:
Zm+1
(mmm)) - 1/mm+1//lllmmaa)))
2 2
(23)
7h 1
Ay C. Ay
Zm+1
<
2
(24)
72
|
Cill
7m+1
2 2
(25)
Zm+1
27m+1
1
1/2 |
(26)
Zm+1
m/
3m3
1C
(27)
Zm+1
Zm++
Let cs/2 3m2'l
It is clear that obtain the linear combination form [Em+1)
Zm+z
mm+1 (m1)))(81) takes time O(m² m² where [1 [fm+1)]]
16

---

Under review as a conference paper at ICLR 2020
cx/2. By Theorem 9, the implementation of state (m++) Tī (90)))] takes time (TH (m + 1)lon(2(m++1/es 1//a))) with error bounds c3/2. Thus, we can implement state (mm+)) = m l9(m))](m++1> by unitary in time O(m² THe -2 +TH (m + 1) with error bounds in 63-
Now we consider the influence of imperfect implementation of state (mm) to Algorithm 3. For simplicity, we neglect the term [[ 19()))| in state ('m) = [[ (9()))))mm) Denote II;
IT 2 (t:l) and I. II: (7 2/t.) (f.)). There is ||T M1|l S 2le3.
Note that the state
10 11)
[nn)
Σ
Imm)
(tm (tm
10)
Σ
(m)) ) (t 1b5))13 }
H
3=1
m=1
in step of Algorithm can be written as:
Σ
14 I |,,
[n;)10) + II:
[1)]
H
2
The probability of generating 0 after the measurement on the last register is:
11 +
Pr
2 11
Similarly we define (0(1)
Σ j=1
M 2 |1,)) + - [,))
|H|
and P1 = | Ejnn 1 |1
D+ 2
|, for the approximate case.
Since the objective of step 5 is obtain the index gl 1) such that the column state (
(814)) is linearly independent from basis {1s;)]= we define p.false as the probability of selecting out the state ( E ( in the approximate case. Note that for state [hz) E ((ss))
(I1, + 1)),;) 0, there
pfa ffass
1 P
Σ
||b3|121
1I + 1
h
H
2
(
|111121 1i++/ |11)11
E
ΣØ= | 1
I1+ [nr)) 1|2
DEi [1 1| N1 TI 111)1
j==1 111,11((122+ + (h1 11, - 11, 1,, + (h ( |1, h2))
12
P2J
Pt LE3
(r-1)e² 4|
lea
Let E3
2
there is:
Σ
r-1
22
r-1
Ic3
r(r-1 1)
2
re²
S
1
2(r () - l)es
Leg
2
8(r
1)
H
16
H
1=0
(28)
3 Thus, by choosing 63 1) H
Algorithm could select out complete basis (1s:) )=
with
probability least 3.
17

---

Under review as a conference paper at ICLR 2020
Note that in Algorithm 3 we need to perform operations R, = I 2 [t] for i = 1,2, 1, which needs the information of parameters {Ci))i=L.j=I- In order to guarantee the success prob- ability of Algorithm 3 (Equation (28)), the estimation on each Cij (sils)) should have error minnecf-1] 2m c². Thus, the estimation on each Gjj bound 6 mr- 6m²]|Cmm" C3 48r"]|C, 1PICH
Zm+1
takes time (TTrr") H ()) and the estimation on the parameter group {ag]]=15=] takes time 4) In order to obtain the description [tm) = Ei= T:). additional time is required for solving (m-II-dimensional equations for 2, 3, 2. 1, which results the time complexity O(r*) in total. With given parameters {zm. m the implementation of operation Rm, = 7 2 fm (tml takes time ( (m + ()) I O(TH - 222 (
(TTHr*
|1 |
Denote Thasis as the required time to implement Algorithm 3 and Tn, as the required time to implement operation R. Since in each iteration of I E [r - 1], Algorithm 3 refers operation R1, Rg. R& for I/P times, there is:
([Tasiis O(THr x
Σ
O(TR.)
Pt
4 H
r-1 Σ 1=0
S 0
+
2
2²
r r-
O(TH
S O(Tmpoly(r)) log 2,
A.8 THE PROOF OF LEMMA 2
Proof. Define the index function g [r] + [d] such that s; hg(s), Vi [r]. Consider the eigen- decomposition of matrix H:
H uu
(29)
It is natural to generate the decomposition:
hj Xuun ())
(30)
hyg= = Σ
nuu u
(k)
(31)
1=1
Define the dimensional matrix C (h (1)) hT
h (hg(1), hg(2). hg(r))-
9(2))
There is:
(ha(e) is linear independent + del(C) (C) # O. Denote the jk-th element of C' as Cyk. Since cyk = hT hv = El= X72 (1)
(32)
u
there is:
Σ X (1(1))
u (0(1)
Σ (0()) u (1(r))
det(C)=
(33)
E X? (a(r)) u
(o(1))
Ei X7n (0(r)) (a(r))
u
X2 ui
(o(1))
(a(1))
x² u
(o(1)) ((())
11
(34)
4=16=1
(g(r)) (1(1))
tx u (o(r)) (
U
(o(1)
(oll)
(35)
4=16=1
1=1
(g(r))
(o(r))
18

---

Under review as a conference paper at ICLR 2020
On the other hand, construct the matrix H' whose jk-tt element is n12x holi).a(k)- There is:
E1=1 Xru (9(1))
(2(1))
Ei=1 A (9(2)) (s(r))
det(H')= =
(36)
Eisl Xuu ) 1000
Ei= seaforr)
u (a(r)
(o(1))
(o(1))
(o(1)) (g(r))
) uir
(37)
(a(1)
(o(r))
(a(r))
Xs, Wis
X Wir
(g()))
(a(1))
II j=l
(oGi)
(38)
1= 1=
(a(r))
(a(r))
Note that the determinant in eq(5)) and eq(38) is non-zero only if km in for any different m, n [r]. Consider the summation of for all j E [r] over {1.2. ... r), there is:
det (C)/ II X - (e
A
(39)
Thus the problem about whether group { Vi-1 is linearly independent could be solved by cal- culating the determinant of matrix H' Since H' is a x dimensional matrix, det(H') could be calculated (rr)) time wwwaarzenberg-Czennee linearly independent if det (H') + 0, or (h 1 linear dependent det(H') (H') 0.
1995). We could claim that the group ( V=
A.9
THE PROOF OF THEOREM
Proof. For Acyl el and !رط S E2, there is:
||C||| S rei and ||b||| S Vrez.
The matrix norm || here denotes the largest singular value of the matrix. Note that elements of matrix C' and vector are overlap of quantum states, which are bounded in [-1,1], so there is:
||||| S and ||b|| S vr.
We have:
|
| ACC+ (C. -| ([|bb| + ||AC C-1bl
1
<|
(||bb) + ||CI|I|*-IIIIbI
1 C-1AC
|C-1|
(Vrrc + 3/2 3/3 C- 2/F
1 ||-1||r
Thus, for u, = E IJ8j and u, = Σラ= 3Js}, there is:
1|u, -ull== = CAr < || ||C1| < 2 2
/r C
A. THE ESTIMATION OF Cij = -0: (8))
The overlap Cty (s, (3) (hg(t) ( can be estimated by the Hadamard Test. We provide the detail in Algorithm 6:
Proposition Algorithm 6 present the e-estimation to the overlap cıg ((s(s)) with probability at least 5 with running time (T 2oTnn=2oog(1//00 log(1/8)).
19

---

Under review as a conference paper at ICLR 2020
Algorithm 6 Cij estimation
Input: Quantum access to oracle UH. The index number i and j. The precision parameter e. The probability error bound 6.
Output: An estimation čij to the value Gjj = (sils)), such that čig E [cis - e Caj + c) with probability at least - 6.
1: for to n = _ log 3) + do
2: Create state [|s.) + 1))
3: Apply the Hadmard gate on the second register to obtain the state العااااااي 10) + اددااادع 11)
2
2
4: Measure the second register and record the result.
5: end for
6: Count the number of resulting in step 4 as m. Output 2m/n 1 as the estimation Cij-
State
[s)) +
(bars +h (a
in step 2 could be generated by performing the following
v2
procedure on state (g())))()))))) 0):
(0) +1)
10(0))00)))11100 (gg()))))))
(40)
v2
Us 00 | (g(()))(())
h (gt))) 10) (0}11)
(41)
v/2
hh a() 10) [hatn)l)>
Us 89 1)(1| (g()))l(())
(42)
V2
trace out the first two registers,
10)
11
(43)
V2
The Hadmard gate in (40) acts on the 4-th register. The gate UH [0] (0) in (41) acts on the 1-st, 3-rd and 4-th registers. The gate UH @ [1}(1] in (42) acts on the 2-nd, 3-rd and 4-th registers.
A.11 THE ESTIMATION OF b, = =(u (s))
The estimation to the overlap b; (u, st) is more complicated. Technics like Algorithm is infea- sible, due to the post-selection method for generating target state uz). Here introduce another standard quantum algorithm named as Quantum Swap Test (Buhrman et al., 2001), which could estimate the square overlap between two quantum states (Φ) and (v).. The eircuit of the Quantum Swap Test illustrated Figure 1.
(0)
H
H
measure
(0)
SWAP
(w)
Figure 1: Circuit of the Quantum Swap Test
As shown in Figure 1, Quantum Swap Test performs the operation:
(0) + (H @ ()((O) (0) & + (1) & US & 1)
(44)
The final state could be written as:
{)) + w + 1 - (+)))))
(45)
The USWAP gate could be implemented time Oppolylog(d) d)). which performs the swap transfor-
mation (6) |xb) (o) for d-dimensional state ()) and (8)) The measurement the first qubit
20

---

Under review as a conference paper at ICLR 2020
produces 0 with probability Po (1 (() Thus, by replacing step 2-3 in Algortihm 6 with the Quantum Swap Test operation, we could build an algorithm to estimate the square of the state overlap.
There exists a quantum algorithum which could present 6-estimation to value D/ ( with probability at least 1 - 5 in running time ( (opaoolylooo() log((1))) where Tinput is the time complexity to generate states |ue) and [st)-
Proposition
In order to estimate values b; = -(4 (s) for E [r]. we need to discriminate the positive and negative of bj. Note that for state (uz).. the state - ute) is also target state which shares the same eigenvalue. So both states (u,) and - -44 are legal outputs and indistinguishable for our algorithm in Section 3.
Thus we analysis the value b; - sgn(u, (A)) (u, (84) the overlap between states /(x) and (st). where u4 is the k-th component of vector ut. Generally ls could be any index such that the corresponding component is non-zero.
Note that by = sgn(u, (*) ( (uelss) = -sgn( (gn((ur (s.).. Define two states |x++) = ž (1hx)) +
(bg(t))) and (b-) = z (Ihx) ())(t))), where Z+ are normalized constants such that 23
2 = 2hh (g())) Then there is:
[(uc/244)1 z (uilhss) (())) + 2( (a) (u) (u)))
(46)
[(ee z (uilha))
( (uullogts) 2(u, (us
(47)
States (xb+) and ( could generated by step 2-4 Algorithm 6. The overlap (hx could be estimated by Algorithm 6. The square overlap (b and (u, |W-)² could be estimated by Quantum Swap Test. Thus for (u, hy(t))l > é', one could discriminate the positive and negative of (u.) hg(n) by calculate the value (2, the square overlap (uu/"/-)) 12 and (u,/yi/) need to have the precision Ku 1hg)1/2 which takes time ("Trmmpet"" 2). For (u, hggo)) S é', O is an é' estimation to (uel (h)g))))) Since an é' e'-sstimation to [b,] could be achieved by an e² ee-estimation to by which takes time (TT (Timpuee' 4)) we could derive the time complexity of estimating b; in Theorem 10.
z (u, j The estimation on
Theorem 10. There exists a quantum algorithm which could present e-sstimation to value b; = sgn(u, (K) Xu,l with probability at least 1- ô in ranning time O (opppooyyyoo( (oo.oolooyol(eeeoo((//o))) log(1/0)). where Timpue is the time complexity to generate states (uu) and \st).
A. GENERATE THE HESSIAN MATRIX
Obtaining the Hessian matrix of a general objective function is computationally expensive. However, the calculation can be simplified in special case. For example, consider the binary classification problem with the sample set Z = {Ix; y, )j E [n]} c Rd x {0, 1}. Consider the non-convex loss function with form: F(x, w) = [h(0) 312 where h : R - R is the non non-linear function such that
h()) T and 0 w² æ + b. Denote 2 (5) the ith component of æz. The total loss function on the set S is defined as f(w) = + ビ F (x,, w) = + ΣT (ww
There is:
0f; 2(h(0,) v,) Oh(0,) (1)
Ov)(
00,
2(h(0,)) v1) (1+c e ) vmll
(48)
=((h(0,) vn)
+ a- - 20/
21

---

Under review as a conference paper at ICLR 2020
ff
a (w((k
(h(0)) - 1/))
e
e
x
awllk)
(1+ (1))-00)
a(h(B,) 8/1)
0 e
(h((0)) VVi) dwok) (1 [1+c 11+e-)))
(w:(k)
(1 - 0,)
E
+ (h((,) v,) (-1) (E -00)) ) e
(4)
(8) (0)
(1 + e e- 1222 -0))2
(1+
(1+e 0=)
2/
Iz
20
2x 1)
(1) (K)
(1+ [1 (h((0) v,) (c -c01)].
(49)
Define
e-2 aj =2
(1+e (h(0,) - Uj) (c c-
(50)
we have:
Virf a
(51)
Thus we could derive the Hessian matrix for the total loss function:
1 fj
1 Σ ajj
H
(52)
n2 w
j=1
Each term in the sum above is rank-1 I matrix, which means the rank of H is bounded by n. Thus, for sparse samples {a,}ý=m with most non-zero elements, we could derive the Hessian as the form {i,, j, hig hug # 0)} in time Onns².. Note that in practical case, d, the dimension of the sample Zy.. be millions large (for example, the number of pixels image), while n, the number of sample involved one iteration of the update, is relatively small.
22


Reviews:
[{"review_id": "ryx_D7wr5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "I am not familiar with the quantum algorithm literature, hence I cannot judge the novelty of the proposed algorithm. Basically, this is a quantum algorithm for computing the smallest negative eigenvalue (and the associated eigenvector) of square matrices. It is worth noting that the algorithm is built on top of the existing SVE model. The authors don't compare this method with any existing work in quantum singular value transformation and decomposition. A throughout discussion and comparison should be made in Section 1.1\n\nDespite the title, I can't find a strong connection between the proposed algorithm and machine learning. Given a loss function f and the parameters x, the paper doesn't specify how to construct the quantum state in the step 2 of Algorithm 2. Is there a cheap way to construct the quantum state from (f, x)? If not, and if one has to compute the Hessian matrix H from (f, x), then the complexity of this pre-processing step will be on the order of O(d^2), which already makes the quantum efficiency meaningless. \n\nEscaping saddle point is usually an iterative process, because the curvature varies across from place to place. The paper focuses on an individual step of a single iteration (i.e. finding the negative curvature), but it doesn't mention how would the iterative process look like.\n\nFinally, although the quantum complexity is poly-log in dimension d, it has a terrible dependence on the rank r and the Frobenius norm of the Hessian matrix. The potential issues of such dependencies should be discussed.\n\n\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "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_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rygZKfH19S", "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 a new quantum algorithm which can efficiently estimate the eigen vectors of a Hessian matrix with negative eigenvalue.\n\nDecision\n\nI would vote for a weak accept although this is somewhat an educated guess. Finding efficient ways to estimate eigen-vectors of the Hessian would have a dramatic impact on second-order optimization techniques (neglecting the practical implications of it being a quantum algorithm). Since the paper is submitted to a machine learning conference I believe more efforts should be done to make the paper accessible to researchers unfamiliar to quantum computing.\n\nComments\n\nI appreciate the clarification of the notation at section 2.1, however many exotic notation for machine learning researchers are presented before this section without any reference to 2.1. The operation `\\propto` (latex) is never explained. My understanding is that it is the update of a quantum state?\n\nThe section 2.2 should give a brief overview of why both techniques will be useful for the many parts of the contributed algorithms.\n\nI could not find definition of T_H anywhere.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "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_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "rkxeWjB6Kr", "reviewer": "AnonReviewer2", "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 a quantum algorithm aiming to solve the eigenvalue decomposition for the Hessian matrix in second-order optimization. The main body of this paper is the quantum singular value decomposition algorithm from Kerenidis & Prakash, 2016. The authors propose some plug-in algorithms in the context of quantum computing. Moreover, this paper does not evaluate the proposed algorithm with any comparative experiments. Personally speaking, it is better to submit the work to the physics journals. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was some support for the ideas presented, but this paper was on the borderline, and ultimately not able to be accepted for publication at ICLR.

Concerns raised included level of novelty, and clarity of the exposition to an ML audience.
Decision: Reject