Title: QUANTUM ALGORITHM FOR FINDING THE NEGATIVE CURVATURE DIRECTION

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 Õ(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.

1. 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 !∇f (x)! ≤ ! g , and

λ min ! ∇ 2 f (x) " ≥ -! H ,

where ! g , ! H ∈ (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 a 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 to escape the saddle points. These algorithms can be divided into the following two categories: the first-order gradientbased algorithms and the second-order Hessian-based algorithms. Generally, second-order algorithms 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 direction, namely, the eigenvector of a Hessian matrix H = ∇ 2 f (x) with negative eigenvalue. This computation could take time O(d 2 ) when the Hessian matrix is given, or O(d/ √ !) when Lanczos method is used with Gradient information to approximate the Hessian-vector product.

Quantum algorithms have shown great potential to become faster alternatives than classical algorithms for many kinds of problems in the field of linear algebra, including principal component analysis (Lloyd et al., 2014) , support-vector machine (Rebentrost et al., 2014) , singular value decomposition (Rebentrost et al., 2018) . These works encourage us to develop an efficient quantum algorithm for finding the negative curvature. To begin with, we formally define the negative curvature finding problem as follows.

Negative Curvature Finding (NCF) problem: Given a function f (x) : R d → R which has L-Lipschitz continuous gradient and the corresponding Hessian , we aim to build a quantum algorithm that could efficiently provide the unit vector u with the condition:

EQUATION

where 0 < α < L and 0 < ! < α; or make the non-vector statement that with high probability there is no unit vector u satisfying the following condition:

u T Hu < -α.

(2)

1.1 RELATED WORK

Optimization methods for non-convex problems can be roughly divided into first-order and secondorder methods, depending on the order of the derivative to the objective function they used. Generally, 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 as a critical subroutine to analyze the characteristic of the saddle point.

First-order algorithms: For the non-convex problem, the first-order method (Gradient-based method) can find the stationary point, which could be a global minima, local minima or 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. Recently 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 a 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-based methods requires O(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 local 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) Hessianbased: 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-vector production, which takes time at least O(d 2 ). 2) Hessian-free: The Hessian-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 O(d! -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 ρ = # d i,j=1 x ij |i〉〈j|, where x ij is the i, j-th element of d × d matrix X with eigen-decomposition X = # rank(X) i=1 λ i u i u i , previous quantum PCA algorithm (Lloyd et al., 2014) could perform the mapping

# j β j |u j 〉 → # j β j |u j 〉| λj 〉 in time O(polylog(d)! -3

). However, the quantum PCA model use the density matrix ρ to store the information of matrix X, which implicitly assumes the condition !X! F = 1 and λ min (X). Another quantum SVD algorithm (Rebentrost et al., 2018) shows an efficient method to estimate the value λ j /d with error ! in time O(! -3 ), for d × d matrix X with eigenvalues {λ j } d j=1 . However, this model only suits the case when λ j /d is relatively large, and it would take time O(d 3 ! -3 ) to produce !-estimation on eigenvalues. Moreover, both of these works did not study the classical read-out of the output state, which generally takes time at least O(d) for d-dimensional state (Aaronson, 2015) , and could offset the claimed quantum speed-up.

1.2. OUR CONTRIBUTION:

The contribution of this work can be briefly divided into two parts: 1) an efficient quantum algorithm to generate the required quantum state, which corresponds to the negative curvature direction, and 2) an efficient quantum algorithm to obtain the description of the target state |u t 〉 = # r i=1 x i |s i 〉, where {s i } r i=1 is an independent vector set selected from columns of Hessian H with rank r. Negative Curvature Finding: We develop an efficient quantum algorithm to produce the target state |u t 〉 (for case (1)) or make the non-vector statement (for case (2)). We provide Proposition 1 as the main result of this part, which guarantees the time complexity of our NCF algorithm: Proposition 1. There exists a quantum algorithm which could solve the Negative Curvature Finding problem in time Õ(polylog(d)poly(r)! -1 ), by providing the target state |u t 〉 (for case (1)), or making the non-vector statement (for case (2)).

Classical Read-out: The classical read-out problem is 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 O(d) (Aaronson, 2015) , and could offset the claimed quantum speed-up. In order to solve this dilemma, we develop an efficient quantum algorithm for the classical read-out of the target state. We notice that the target state |u t 〉 can be written as the linear combination form |u t 〉 = # r i=1 x i |s i 〉, where {s i } r i=1 is a linearly independent basis sampled from column vectors {h j } d j=1 . 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 |u t 〉 = # r i=1 x i |s i 〉 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 two subroutines named as the Complete Basis Selection and the State Overlap Estimation. The main results about the Complete Basis Selection and the Classical Read-out are briefly summarized as following theorems:

Theorem 1. There exists a quantum algorithm which takes time Õ(poly(r)! -2 r c ) to find an index set {g(i)} r i=1 , where r is the rank of H, c = 2 log 4r"H" F ! and {g(i)} r i=1 forms a complete basis {|h g(i) 〉} r i=1 with probability at least 3/4. Theorem 2. The classical description of the target state |u t 〉 = # r i=1 x i |s i 〉 could be presented in time Õ(polylog(d)poly(r)! -5 ) with error bounds in ! 2 , when the basis set {s j } r j=1 is given.

The rest of this paper is organized as follows. Some preliminaries about quantum information are introduced in Section 2. In Section 3, we develop an quantum algorithm to solve the NCF problem. In Section 4, we develop an quantum algorithm which aims to read out 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 a standard notation in quantum mechanics to describe the quantum states. The form |x〉 is the state which corresponds to the vector x, and the form 〈y| is the state which corresponds to the vector y T . The notation 〈y|x〉 denotes the value y T x/(!y!!x!). The notation |y〉〈x| denotes the matrix yx T /(!y!!x!). Quantum state is unitary, which means !|x〉! 2 = 〈x|x〉 = 1. Thus for vector x ∈ R d , the state |x〉 is defined as

# d j=1 x j /!x!|j〉

, where x j is the j-th component of vector x and {|j〉} d j=1 is the state basis which acts like {e j } d j=1 in classical case. One could obtain information from the quantum state by performing measurement. For example, the measurement of |x〉 on the basis {|j〉} d j=1 could randomly produce different index j with probability x 2 j /!x! 2 . We use [n] to denote the set {1, 2, • • • , n}. We denote the norm ! • ! as the ! • ! 2 norm for vector and the spectral norm for matrix, if there is no more explanation.

!A! F = ( # m i=1 # n j=1 a 2 ij ) 1/2

is the Frobenius norm of matrix A ∈ R m×n . The lowercase form h i is defined as the i-th column vector of matrix H ∈ R d×d . x i is defined as the i-th component of vector x. The tensor product of two matrix A ∈ R m×n and B ∈ R p×q is defined as C = A ⊗ B. The tensor product operation could be performed between vectors, since vector is one special kind of matrix. The tensor product could be defined between quantum states |x 1 〉 and |x 2 〉 which is written as |x 1 〉|x 2 〉. We present definitions of smoothness and γ-separation here.

Definition 1. (smoothness) A function f : R d → R is L-smooth if it has L-Lipschitz continuous gradient, that is !∇f (x) -∇f (y)! ≤ L!x -y!, ∀x, y ∈ X , where X is the domain of f (x). Definition 2. (γ-separation) The set G = {a 1 , a 2 , • • • , a n } is said to be γ-separated if |a i -a j | > γ, ∀i, j ∈ [n] and i ∕ = j.

Based on these definitions, we assume that the Hessian H in this article has two properties:

1. Hessian H ∈ R d×d is a r-rank matrix; 2. The absolute value of H's non-zero eigenvalue is !-separated.

The first property is directly derived from the assumption of previous classical non-convex optimization method (Carmon et 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 = # r j=1 λ j u j u T j 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 existence of following quantum oracles, and discuss the query complexity of our algorithms to these oracles. Given Hessian H ∈ R d×d , we assume that H is stored in a classical data structure such that the following quantum oracles could be implemented:

U H : |i〉|0〉 → |i〉|h i 〉 = 1 !h i ! d $ j=1 h ij |i〉|j〉, ∀i ∈ [d],

(3)

EQUATION

where h stands for the d-dimensional vector whose i-th component is

!h i !/!H! F .

The required data structure has a binary tree form. The sign and square value for each entry are 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 H as the time complexity of these oracles.

Quantum Singular Value Estimation (SVE): Given matrix H ∈ R d×d which has the eigenvalue decomposition H = # r j=1 λ j u j u j , previous work (Kerenidis & Prakash, 2016) provided a quantum 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

# j β j |u j 〉 → # j β j |u j 〉| | λ j |〉 with time complexity O(T H polylog(d)! -1 ), where λj ∈ [λ j -!!H! F , λ j + !!H! F ] with probability at least 1 -1/poly(d).

3. 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 t 〉 (for case (1)) or making the non-vector statement (for case (2)). The target state |u t 〉 corresponds to the eigenvector u t which satisfies the condition u T t Hu t ≤ -α + !/2. Here we present a tighter restrict on the target state |u t 〉 to keep a !/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 5 in Appendix) as subroutines proposed in Section 3.2 and Section 3.3, respectively.

Algorithm 1 Quantum Negative Curvature Finding (Quantum NCF) Algorithm Input: Quantum access to oracles U H and V H . The parameter ! and α in the NCF problem. Output: The target state |u t 〉 whose corrsponding classical unit vector u t satisfies the condition u T t Hu t ≤ -α + !/2; or a statement with high probability that there is no such kind of unit vector u which satisfies the condition u T Hu ≤ -α. 1: Label the proper(less than -α + !/2) eigenvalue of H (Proper Eigenvalue Labelling). 2: if the least eigenvalue of H is less than -α + !/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 T Hu ≤ -α. 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 eigenvectors with negative eigenvalues. Hence, we cannot directly apply the quantum SVE algorithm since it only gives the estimation on |λ j |. In order to overcome this critical issue, we develop Algorithm 4 in Appendix to label negative eigenvalues.

Secondly, since the quantum SVE Algorithm presents !-estimation on singular values with time complexity O(T H !H! F polylog(d)! -1 )(Theorem 3), we need to provide a tight upper bound for the Frobenius norm !H! F , which is shown in Lemma 1: Lemma 1. Suppose H ∈ R d×d is the Hessian matrix derived from the function f : R d → R which has the L-Lipschitz continuous gradient. Thus the Frobenius norm of H has the upper bound !H! F ≤ √ rL, where r is the rank of H.

Finally, the input-state problem. For the general superposition state # j β j |u j 〉, the output state of quantum SVE algorithm has the form # j β j |u j 〉|| λj |〉. We could generate different pure state |u j 〉 with probability |β j | 2 by the measurement on eigenvalue register. Thus in order to guarantee a small time complexity, we need to prepare a 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 1 in Proposition 2. Proposition 2. Algorithm 1 takes time O(T H !H! 5 F polylog(d)! -1 ) to solve the negative curvature finding problem by providing the target state |u t 〉 or making the statement that there is no unit vector satisfies the condition u T Hu ≤ -α.

3.2. POSITIVE-NEGATIVE EIGENVALUE DISCRIMINATION:

In this section, we propose an algorithm aiming to label the target eigenvalue which is less than -α+ !/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 2 to 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 -α + !/2. We view this kind of eigenvalue as our target eigenvalue.

The mean idea of Algorithm 2 is to use the input state 1 "H" F # r j=1 λ j |u j 〉|u j 〉 for the quantum SVE model and obtain the state:

1 !H! F r $ j=1 λ j |u j 〉|u j 〉|| λj |〉.

The measurement on the eigenvalue register would lead this entangled state collapse to different states |u j 〉|u j 〉 for j ∈ [r]. We could obtain the state |u j 〉 by neglecting the state in any other register. Using state |u j 〉 to apply the PNED algorithm (Algorithm 4 in appendix) could provide a discrimination on the positive and negative of the corresponding eigenvalue λ j . Thus, we could label the proper eigenvalue, for the case that the least eigenvalue is less than -α + !/2; or make the Algorithm 2 Proper Eigenvalue Labelling Input: Quantum access to oracles U H and V H . The parameter ! and α in the NCF problem. Output: A proper label to the singularvalue |λ j | such that λ j ≤ -α + !/2 with probability 1 -δ, or a non-vector statement that there is no unit vector u which satisfies u T Hu < -α.

1: for k = 1 to 4"H" 2 F α 2 (2 4"H" 2 F α 2 log 1 δ + 3) do 2:

Create the state 1 "H" F # r j=1 λ j |u j 〉|u j 〉.

3::

Apply the quantum SVE model to obtain the state 1

"H" F # r j=1 λ j |u j 〉|u j 〉|| λj |〉, where | λj | ∈ |λ j | ± !/4 with probability 1 -1/poly(d).

4::

Measure the eigenvalue register and mark the result.

Use the rest state in the first register as the input to apply the PNED algorithm. 10:

if | λj | < α -!/4

, then make the no-vector statement;

11:

else, label eigenvalue λ j as the proper eigenvalue.

12:

end if 13: end if non-vector statement, for the case that all of eigenvalues are greater than -α. We present the time complexity of Algorithm 2 in Theorem 4.

Theorem 4. Algorithm 2 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 T Hu < -α, with time complexity O(T H !H! 5 F polylog(d)! -1 ).

3.3. TARGET STATE GENERATING:

Suppose the result of Algorithm 2 implies the existence of the target eigenvector u t , which satisfies u T t Hu t ≤ -α + !/2. Then in order to give a solution to the NCF problem, we need to obtain the vector u t . In this section we construct a quantum procedure to generate the state |u t 〉. The classical read-out of |u t 〉, which means to estimate vector u t from quantum state |u t 〉, will be discussed in the following section. The idea is very similar to Algorithm 2. We still use state 1 "H" F # r j=1 λ j |u j 〉|u j 〉 as the input of quantum SVE algorithm to obtain state:

1 !H! F r $ j=1 λ j |u j 〉|u j 〉|| λj |〉.

Suppose λ t denotes the eigenvalue of |u t 〉 that λ t ≤ -α + !/2. The measurement on the eigenvalue register could generate state |u t 〉|u t 〉 with probability 

P t = λ 2 t "H" 2 F ≥ α 2 4"H" 2 F . Thus the probability of generating at least one state |u t 〉 in N = % 4 "H" 2 F α 2 log 1 δ & + 1 times of measurement is 1 - (1 -P t ) N . There is: 1 -(1 -P t ) N ≥ 1 -e -N Pt ≥ 1 -e -log(1/δ) = 1 -δ.

!H! 3 F polylog(d)! -1

) with probability at least 1 -1/poly(d).

4. STATE READ-OUT:

In this section, we propose an efficient algorithm to read-out the classical vector u t from the quantum state |u t 〉. Generally, the classical read-out of a d-dimensional quantum state takes at least Õ(d) times of measurement to obtain the form |x〉 = # d i=1 x i e i . 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, we propose a quantum-classical hybrid procedure to rewrite the target state |u t 〉 as the linear combination of r 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 |u t 〉 = # r i=1 x i |h g(i) 〉1 could be presented in time O(T H polylog(d)poly(r)! -5 ) with error bounds in !/2, when the complete basis set {h g(j) } r j=1 is given.

Recall that our Hessian matrix H ∈ R d×d has the eigendecomposition H = # r j=1 λ j u j u T j , where λ j is the eigenvalue of H with respect to eigenvector u j . Then, any eigenvector of H that corresponds to a non-zero eigenvalue could be represented as the linear combination of vectors in {h j } d j=1 because Hu j = λ j u j can be written as

# d i=1 h i u (i) j = λ j u j .

Since H has the rank of r, there exists a subset of complete basis {h g(i) } r i=1 of the column space, which is sampled from the set {h j } d j=1 . Thus, any eigenvector u j could also be represented as the linear combination of vectors in {h g(i) } r i=1 . Back to the state read-out problem, denote s i as h g(i) for simplicity. Suppose the target state |u t 〉 that we generated in the previous section can be written as

|u t 〉 = # r i=1 x i |s i 〉, where {x i } r i=1

are coordinates of the state |u t 〉 under the basis {|s i 〉} r i=1 . Thus, instead of simply reading out components of vector u t , we could get the classical description of |u t 〉 by calculating each x i . Note that the complete basis {|s i 〉} r i=1 is not unique and we only need to identify one of them. We also notice some recent breakthroughs about quantum-inspired 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 as the linear-sum on a group of column vectors. However, in order to cover the whole column space, the quantum-inspired algorithm need to sample at least O( r 2 ! 2 ) number of columns as basis, while our method generate the linear-sum form exactly on r columns.

4.1. COMPLETE BASIS SELECTION:

In this section, we develop a quantum algorithm to select a subset S I = {g(1), g(2), • • • , g(r)} from [d] , which corresponds to the complete basis {|h g(i) 〉} r i=1 . The quantum complete basis selection algorithm can be viewed as the quantum version of Gram-Schmidt orthogonalization: firstly we choose |t 1 〉 = |h g(1) 〉 from the set {|h j 〉} d j=1 ; then given state set {|t m 〉} l m=1 , we choose

|t l+1 〉 ∝ |h g(l+1) 〉 - # l m=1 |t m 〉〈t m |h g(l+1) 〉 from the state set {|h j 〉 - # l m=1 |t m 〉〈t m |h j 〉} d j=1 . Since the chosen |t l+1 〉 is orthogonal to states {|t m 〉} l m=1 for each iteration l ∈ [r-1], the state set {|t m 〉} r m=1

forms an orthonormal basis. Note that the state |t m 〉 is generated along with an index g(m) for m ∈ [r], so we would obtain a complete basis index set {g(m)} r m=1 after the implementation of this quantum algorithm. The quantum complete basis selection algorithm is provided in Algorithm 3, in which we denote:

EQUATION

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 {s i } r i=1 are linearly independent. Theorem 6. The Algorithm 3 takes time O(T H poly(r)! -2 r 2 log(4r"H" F /!) ) to find an index set {g(i)} r i=1 , which forms a complete basis {|h g(i) 〉} r i=1 with probability at least 3/4.

Algorithm 3 Complete Basis Selection:

Input: Quantum access to oracle U H and V H . Output: The index set of the complete basis: S I = {g(i)} r i=1 . 1: Initialize the index set S I = ∅. 2: for l = 0 to r -1 do 3:

Create the state |φ (l) 1 〉 defined in Equation ( 5).

Measure the third register of state |φ (l) 1 〉 multiple times to get the state |φ

(l) 2 〉 which is pro- portional to 1 "H" F # d j=1 |j〉!h j ! % |h j 〉 - # l m=1 |t m 〉〈t m |h j 〉

& .

Measure the first register and record the result as g(l + 1).

6::

Denote |t l+1 〉 as the state proportional to |h g(l+1) 〉 -# l m=1 |t m 〉〈t m |h g(l+1) 〉.

7::

Update the index set S I = S I ∪ {g(l + 1)}. 8: end for Lemma 2. It takes O(r 3 ) time to check whether the vector set {s i } r i=1 is linearly independent when the classical access to Hessian H is given, where s i is sampled from column vectors of matrix H. We propose several methods in Appendix to estimate overlap b i = 〈u t |s i 〉 and c ij = 〈s i |s j 〉, which are based on the Quantum SWAP Test (Buhrman et al., 2001) and the Hadamard Test. Our proposed quantum algorithms could present ! 1 -estimation to

c ij = 〈s i |s j 〉 in time O(T H ! -2 1 ) and ! 2 -estimation to b i = 〈u t |s i 〉 in time O((T Input + T H )! -4

2 ), where T Input is the time to generate state |u t 〉. Since the time complexity to generate the target state is O(T H !H! 3 F polylog(d)! -1 ) as proposed in Theorem 5, we could derive Proposition 3.

Considering the time complexity O(T H !H! 5:

F polylog(d)! -1 ) to label the proper eigenvalue and the time complexity O(T H poly(r)! -2 r 2 log(4r"H" F /!) ) to generate the complete basis set, we could solve the NCF problem in time O(T H polylog(d)poly(r)! -2 (! -3 + r 2 log(4r"H" F /!) )) by providing the target vector in the form

u t = # r i=1 x i h g(i) /!h g(i)

! with error bounded by ! or making the non-vector statement.

5. CONCLUSION:

We propose an efficient quantum algorithm for the Negative Curvature Finding problem, which is a critical subroutine in many second-order methods for non-convex optimization. The proposed quantum algorithm could produce the target state in time O(T H ! -1 poly(r)polylog(d)) with probability 1 -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 O(T H poly(r)polylog(d)! -2 (! -3 + r 2 log(4r"H" F /!) )), which is exponentially faster on the degree of d than existing general quantum state read-out methods. 

A APPENDIX:

A.1 THE PROOF OF THEOREM 2

Proof. The time complexity of Algorithm 1 could be directly obtained by the time complexity of Algorithm 2 and Algorithm 5, whose complexity analysis are presented in Theorem 4 and Theorem 5, respectively.

A.2 THE PROOF OF LEMMA 1

Proof. Assume λ 1 ≤ λ 2 ≤ • • • ≤ λ d are eigenvalues of H, we have: min "v"=1 v T Hv ≤ λ j ≤ max "v"=1 v T Hv, ∀j ∈ [d].

By the definition of the Hessian matrix, for unit vector v, we have:

Hv = ∇ 2 f (x)v = lim h→0 ∇f (x + hv) -∇f (x) h .

From above equation, we can obtain:

v T Hv ≤ !v! • !Hv! ≤ lim h→0 "∇f (x+hv)-∇f (x)" h ≤ lim h→0 L"hv" h = L,

and v T Hv ≥ -!v! • !Hv! ≥ -lim h→0 "∇f (x+hv)-∇f (x)" h ≥ -lim h→0 L"hv" h = -L.

Thus, the eigenvalue λ j is bounded in [-L, L] for all j ∈ [d].

We have

!H! 2 F = # i # j h 2 ij = T r(H • H) = # j λ j (H 2 ) ≤ rL 2 , so !H! F ≤ √ rL.

Lemma 3. Hoeffding's inequality (Hoeffding, 1994 )

EQUATION

and

EQUATION

A.3 THE DETAIL ABOUT ALGORITHM 4

In Algorithm 4, P ∈ R d 2 ×d is the matrix whose column vector p i = e i ⊗ hi "hi" for i ∈ [d] , and Q ∈ R d 2 ×d is the matrix whose column vector q j = h "H" F ⊗ e j for j ∈ [d]. h i is the i-th column vector of matrix H and h is a d-dimensional vector whose i-th component is !h i !. It can be directly obtained that the matrix P and Q satisfy the decomposition H/!H! F = P T Q and have property 

P T P = Q T Q = I.

= 2[ "H" 2 F a 2 log 1

δ -1 2 ] + 3 times, to make a statement that λ is positive or negative, with probability 1 -δ.

Proof. The measurement in step 6 of Algorithm 4 outputs 1 with probability:

EQUATION

Note that 〈P u|Qu〉 = u T P T Qu = 1 "H" F u T Hu = λ "H" F , so P (1) = 1-λ/"H" F

2:

. Similarly we have P (0) = 1+λ/"H" F

.

Suppose that we need 2x + 1 times of measurement to give an 1 -δ correct statement about whether λ > 0 or λ < 0. The problem can be viewed as the biased coin problem. Define random variables X i such that P (X i = 1) = p and P (X i = 0) = 1 -p and S n = # n i=1 X i . Then there has the Hoeffding's inequality P (S n /n -p ≤ -!) ≤ e -2n! 2 and P (S n /n -p ≥ !) ≤ e -2n! 2 . Back to the problem, suppose λ < 0, by setting n = 2x + 1, n(p -!) = x and P = 1-λ/"H" F 2 , we have:

P (S 2x+1 ≤ x) ≤ exp(-2(2x + 1)[ 1 -λ/!H! F 2 - x 2x + 1 ] 2 ) < e -2x+1 2 λ 2 "H" 2 F ≤ e -2x+1 2 a 2 "H" 2 F .

Similarly for λ > 0, there is

P (S 2x+1 ≥ x) ≤ e -2x+1 2 a 2 "H" 2 F . Let e -2x+1 2 a 2 "H" 2 F ≤ δ , we have x ≥ [ "H" 2 F a 2 log 1 δ -1 2 ] + 1.

A.4 THE PROOF OF THEOREM 4:

Proof. The input state 1 "H" F # r j=1 λ j |u j 〉|u j 〉 could be generated with oracles U H and V H :

EQUATION

)

Since H has the eigen-decomposition

H = # r k=1 λ k u k u T k , we could rewrite entry h ij as h ij = # r k=1 λ k u (i) k u (j) k , where u (i) k

is the i-th component of vector u k . Thus the state

1 "H" F # d i=1 # d

j=1 h ij |i〉|j〉 could be written as:

1 !H! F d $ i=1 d $ j=1 r $ k=1 λ k u (i) k u (j) k |i〉|j〉 = 1 !H! F r $ k=1 λ k |u k 〉|u k 〉.

Then we apply the quantum SVE model on this state. In order to give !/4-estimation on the singular value, the time complexity to run the quantum SVE algorithm is O(T H !H! F polylog(d)! -1 ) by Theorem 3. Suppose there are eigenvalues λ j which are less than -α + !/2. We denote the least one as λ t and label it as the proper eigenvalue. By Theorem 8, we need to generate

n t = 2[ "H" 2 F λ 2 t log 1

δ -1 2 ] + 3 numbers of state |u t 〉 in order to guarantee that λ t < 0 with probability 1 -δ. Note that the probability of generating state |u t 〉 in each iteration of step 2-4 in Algorithm 2 is

P t = λ 2 t "H" 2 F .

So averagely we need to perform step 2-4 in Algorithm 2 for n =

"H" 2 F λ 2 t {2[ "H" 2 F λ 2 t log 1 δ -1 2 ] + 3} times.

The number n can be roughly upper bounded by

4"H" 2 F α 2 (2 4"H" 2 F α 2 log 1 δ +3), since for negative curvature case ! < α, we have |λ t | = α -!/2 > α/2.

By considering the time complexity to run the quantum SVE algorithm (O(T H !H! F polylog(d)! -1 )) and setting the probability error bound δ = 1/poly(d), we could derive that the time complexity of Algorithm 2 is O(T H !H! 5 F polylog(d)! -1 ).

A 

〉 = λ t ≤ -α + !/2. 1: for k = 1 to % 4 "H" 2 F α 2 log 1 δ & + 1 do 2:

Create the state 1 "H" F # r j=1 λ j |u j 〉|u j 〉.

Apply the quantum SVE model to obtain the state 1 "H" F # r j=1 λ j |u j 〉|u j 〉|| λj |〉, where | λj | ∈ |λ j | ± !/4 with probability 1 -1/poly(d).

Measure the eigenvalue register and mark the result.

if the eigenvalue measured in in step 4 is labelled to be proper in Algorithm 2, then 6:

output the state in the first register as the target state. 

EQUATION

we note that the state |φ

(l)

1 〉 in Step 3 of Algorithm 3 can be generated by the following procedure:

EQUATION

EQUATION

EQUATION

)

In step (a), we employ the quantum oracles U H V H on ancillas |0〉|0〉. In step (b), an auxiliary register |0〉 is appended, followed by a Hadamard gate. In step (c), we apply operation

2 l m=1 [R m ⊗ |0〉〈0| + I ⊗ |1〉〈1|]. The operation R m is defined on the register |g(1)〉, • • • |g(m)〉, |h j 〉: R m = I ⊗(m+1) -2 ' % m + j=1 |g(j)〉 & |t m 〉 (' % m + j=1 〈g(j)| & 〈t m | ( .

In step (d), we apply the Hadamard gate on the auxiliary register. In step (e), we trace out registers 2 l j=1 |g(j)〉 to generate state |φ (l) 1 〉. The crucial part in Algorithm 3 is to implement the reflection R m . For the m + 1 case, there is:

EQUATION

Note that {|t i 〉} forms the orthogonal basis: 〈t i |t j 〉 = 0, ∀i ∕ = j, and

Z m+1 = 〈t m+1 |s m+1 〉 = !|s m+1 〉 - # m i=1 |t i 〉〈t i |s m+1 〉! = 3 1 - # m i=1 〈t i |s m+1 〉 2 . Denote |t i 〉 ≡ # i j=1 x ij |s j 〉.

The restriction that |t m+1 〉 is normalized and orthogonal to states 17): 4 5 5 5 5 5 6 5 5 5 5 5 7

|s 1 〉, |s 2 〉, • • • |s m 〉 could yield Equation (

EQUATION

Note that x m+1,m+1 = 1/Z m+1 by Equation ( 16). Define the m-dimensional vectors x, b, and the m × m matrix C m to be:

x = m $ i=1 x m+1,i e i , b = m $ j=1 〈s j |s m+1 〉e j , C m = {c ij ≡ 〈s i |s j 〉} m,m i,j ,

where each value c ij = 〈s i |s j 〉 could be estimated by Hadamard Test. Thus, we could derive the following linear equations about x from Equation (17): 4 5 5 6 5 5 7

EQUATION

We could obtain the coordinate {x m+1,i } m+1 i=1 by solving Equation (18). There is: 4 5 5 5 5 6 5 5 5 5 7

EQUATION

where matrix

C (i)

m denotes the matrix generated from C m by replacing the i-th column with b.

Suppose now we have obtained the linear combination form |t m+1 〉 = # m+1 i=1 x m+1,i |s i 〉. Thus, we could construct a unitary to generate the state

% 2 m+1 j=1 |g(j)〉 & |t m+1 〉 from the state % 2 m+1 j=1 |g(j)〉 & |0〉

, by the linear-combination-of-states method (Shao, 2018).

The idea of linear combination of states was introduced in Shao ( 2018), which focuses on the following problem: given quantum states |a〉 and |b〉, to prepare the state |c〉 = 1 Zc (x|a〉 + y|b〉). The method is based on the fact that R 2θ = (I -2|b〉〈b|)(I -2|a〉〈a|) can be viewed as the clockwise rotation in the plane spanned by |a〉 and |b〉 with angle 2θ, where θ = arccos〈a|b〉 is the angle between |a〉 and |b〉. Thus any clockwise rotation in space SP AN {|a〉, |b〉} with angle φ could be written as

R φ = R φ/2θ 2θ . For the case |c〉 = 1 Zc (x|a〉 + y|b〉), there is |c〉 = R φ |a〉, where φ = arccos x+y〈a|b〉 Zc = arccos x+y〈a|b〉 √ x 2 +y 2 +2xy〈a|b〉

. The linear sum of 2 states could be generalized to n case: 

2 l m=1 [R m ⊗ |0〉〈0| + I ⊗ |1〉〈1|] could be performed by 2 l m=1 9 : U † m+1 (I -2|0〉〈0|)U m+1 ; ⊗ |0〉〈0| + I ⊗ |1〉〈1| < .

A.7 THE PROOF OF THEOREM 6

Denote P l as the probability of resulting 0 after the measurement in Step 4 of Algorithm 3. In order to generate the required state, the measurement in Step 4 needs to be performed for O(1/P l ) times.

The Lemma 4 provides a lower bound on P l .

Lemma 4. The probability of resulting 0 after the measurement in Step 4 of Algorithm 3 as the lower bound

P l ≥ (r-l)! 2 4"H" 2 F . Proof. Suppose λ 2 1 ≥ λ 2 2 ≥ • • • ≥ λ 2 r

, where λ i is the eigenvalue of H. Since state |t m 〉 is the linear sum of {|h j 〉} d j=1 , we can assume that |t m 〉 has the decomposition

|t m 〉 = # r i=1 w mi |u i 〉, for all m = 1, 2, • • • , l

, where # r i=1 w mi w ni = δ mn . There is:

P l = 1 !H! 2 F d $ j=1 = !h j ! 2 !|h j 〉 - l $ m=1 |t m 〉〈t m |h j 〉! 2 > = 1 !H! 2 F d $ j=1 = !h j ! 2 - l $ m=1 !h j ! 2 |〈t m |h j 〉| 2 > = 1 - 1 !H! 2 F d $ j=1 l $ m=1 = r $ i=1 w mi λ i u (j) i > 2 = 1 - 1 !H! 2 F d $ j=1 l $ m=1 ) * r $ i=1 w 2 mi λ 2 i (u (j) i ) 2 + r $ i∕ =k w mi w mk λ i λ k u (j) i u (j) k , - = 1 - 1 !H! 2 F l $ m=1 r $ i=1 w 2 mi λ 2 i = 1 - 1 !H! 2 F r $ i=1 c i λ 2 i ,

where

c i = # l m=1 w 2 mi . Consider the r-dimensional vector w m = # r i=1

w mi e i . The vector set {w m } l m=1 forms an orthogonal basis in a l-dimensional subspace. Note that we can add w l+1 , • • • w r such that {w m } r m=1 forms an orthonormal basis in the whole r-dimensional space. Denote matrix

EQUATION

Thus we have the upper bound:

c i = # l m=1 w 2 mi ≤ # r m=1 w 2 mi = 1. Note that # r i=1 c i = # r i=1 # l m=1 w 2 mi = # l m=1

# r i=1 w 2 mi = l, so there is:

EQUATION

Note that for the case |λ i | ≤ !/2, λi = 0 is a good estimation for the NCF problem, so we could further assume |λ i | > !/2 for the general case and bound the inequality (21) as

P l ≥ (r-l)! 2 4"H" 2 F .

The error of implementing |t m+1 〉 comes from the imperfect implementing of the linearcombination-of-states operation and the error of calculating x. The former has been analyzed in Theorem 9. The error of calculating x is more complex. So there is:

!∆y! = !(C m + ∆C m ) -1 (∆b -∆C m • C -1 m b)! ≤ !C -1 m ! • !(I + C -1 m ∆C m ) -1 ! • (!∆b! + !∆C m • C -1 m b!) ≤ !C -1 m ! • 1 1 -!C -1 m ∆C m ! • (!∆b! + !∆C m !!C -1 m !!b!) ≤ !C -1 m ! 1 -!C -1 m !m! 1 • ( √ m! 1 + m 3/2 ! 1 !C -1 m !) ≤ 2m 3/2 !C -1 m ! 2 ! 1 1 -!C -1 m !m! 1 .

The norm !C -1 m ! here denotes the largest norm of eigenvalues of matrix C -1 m . Thus, for

! 2 = 3m 3/2 !C -1 m ! 2 ! 1 , we have bound !∆y! ≤ ! 2 . For |t m+1 〉 = # m+1 i=1 x m+1,i |s i 〉 and | tm+1 〉 = # m+1 i=1 xm+1,i |s i 〉,

there is:

〈t m+1 | tm+1 〉 = m+1 $ i=1 m+1 $ j=1 x m+1,i c ij xm+1,j = 1 Z m+1 Zm+1 [ m,m $ i=1,j=1 y i c ij ỹj - m $ i=1 y i b i - m $ j=1 b j ỹj + 1] = 1 Z m+1 Zm+1 [1 - m $ i=1 y i b i ] = Z m+1 Zm+1 .

Note that the form | tm+1 〉 = # m+1 i=1 xm+1,i |s i 〉 is not a normalized state:

!| tm+1 〉! 2 = m+1 $ i=1 m+1 $ j=1 xm+1,i c ij xm+1,j = 1 Z2 m+1 [ m,m $ i=1,j=1 ỹi c ij ỹj + 1 -2 m $ i=1 ỹi b i ] = 1 Z2 m+1 [ m,m $ i=1,j=1 ∆y i c ij ∆y j + 2 m,m $ i=1,j=1 ∆y i c ij y j + m,m $ i=1,j=1 y i c ij y j + 1 -2 m $ i=1 ∆y i b i -2 m $ i=1 y i b i ] = 1 Z2 m+1 [Z 2 m+1 + m,m $ i=1,j=1 ∆y i c ij ∆y j ].

Thus, the overlap between state |t m+1 〉 and | tm+1 〉 is:

EQUATION

)

There is:

EQUATION

) Let ! 3 /2 = 3m 2 "C -1 m " 2 !1 Zm+1

. It is clear that to obtain the linear combination form 

| tm+1 〉 = # m+1 i=1 xm+1,i |s i 〉 takes time O(m 3 + m 2 T H ! -2 1 ), where !| tm+1 〉/!| tm+1 〉! -|t m+1 〉! ≤ ! 3 /2.

2 m j=1 |g(j)〉]|t m 〉. Denote Π l = 2 l i=1 (I -2|t i 〉〈t i |) and Πl = 2 l i=1 (I -2| ti 〉〈 ti |). There is !Π l -Πl ! ≤ 2l! 3 . Note that the state |φ (l) 1 〉 = 1 !H! F d $ j=1 !h j !|j〉 0= |h j 〉 - l $ m=1 |t m 〉〈t m |h j 〉 > |0〉 - l $ m=1 |t m 〉〈t m |h j 〉|1〉

1 in step 3 of Algorithm 3 can be written as:

1 !H! F d $ j=1 !h j !|j〉[ Π l + I 2 |h j 〉|0〉 + Π l -I 2 |h j 〉|1〉].

The probability of generating 0 after the measurement on the last register is:

P l = 1 !H! 2 F d $ j=1 !h j ! 2 ! Π l + I 2 |h j 〉! 2 .

Similarly we define | φ(l)

1 〉 = 1 "H" F # d j=1 !h j !|j〉[ Πl +I 2 |h j 〉|0〉 + Πl -I 2 |h j 〉|1〉],

and Pl = 1

"H" F # d j=1 !h j ! 2 ! Πl +I 2 |h j 〉! 2

for the approximate case. Since the objective of step 5 is to obtain the index g(l + 1) such that the column state |h g(l+1) 〉 = |s l+1 〉 is linearly independent from basis {|s i 〉} l i=1 , we define P f alse l as the probability of selecting out the state |s l+1 〉 ∈ {|s i 〉} l i=1 in the approximate case. Note that for state |h j 〉 ∈ {|s i 〉} l i=1 , (Π l + I)|h j 〉 = 0, so there is:

EQUATION

Thus, by choosing ! 3 = ! 2 8(r-1)"H" 2 F , Algorithm 3 could select out a complete basis {|s i 〉} r i=1 with probability at least 3 4 .

Under review as a conference paper at ICLR 2020 Note that in Algorithm 3 we need to perform operations R

i = I -2|t ′ i 〉〈t ′ i | for i = 1, 2, • • • , r -1, which needs the information of parameters {c ij } r-1,r-1 i=1,j=1

. In order to guarantee the success probability of Algorithm 3 (Equation ( 28)), the estimation on each c ij = 〈s i |s j 〉 should have error bound

! 1 = min m∈[r-2] Zm+1 6m 2 "C -1 m " 2 ! 3 ≥ min m∈[r-1] Zm 48r 3 "C -1 r " 2 "H" 2 F ! 2 . Thus, the estimation on each c ij takes time O(T H r 6 !H! 4 F ! -4

) and the estimation on the parameter group {c ij } r-1,r-1 i=1,j=1 takes time O(T H r 8 !H! 4 F ! -4 ). In order to obtain the description |t m 〉 = # m i=1 x m,i |s i 〉, additional time is required for solving (m-1)-dimensional equations for m = 2, 3, • • • r -1, which results the time complexity O(r 4 ) in total. With given parameters {x m,i } m i=1 , the implementation of operation

R m = I -2|t ′ m 〉〈t ′ m | takes time O(T H (m + 1) log(2(m+1)/!3) ) ≤ O(T H • r 2 log(4r"H" F /!)

). Denote T basis as the required time to implement Algorithm 3 and T Ri as the required time to implement operation R i . Since in each iteration of l ∈

EQUATION

It is natural to generate the decomposition:

EQUATION

h jk = r $ i=1 λ i u (j) i u (k) i . (31) Define the r × r dimensional matrix C = (h T g(1) , h T g(2) , • • • , h T g(r) ) T (h g(1) , h g(2) , • • • , h g(r)

). There is:

EQUATION

Denote the jk-th element of C as c jk . Since

c jk = h T j h k = # r i=1 λ 2 i u (j) i u (k)

i , there is:

EQUATION

)

On the other hand, construct the matrix H ′ whose jk-th element is h ′ jk = h g(j),g(k) . There is:

EQUATION

)

Note that the determinant in eq(35) and eq(38

) is non-zero only if i m ∕ = i n for any different m, n ∈ [r].

Consider the summation of i j for all j ∈ [r] over {1, 2, • • • , r}, there is:

EQUATION

Thus the problem about whether group {h g(i) } r i=1 is linearly independent could be solved by calculating the determinant of matrix H ′ . Since H ′ is a r × r dimensional matrix, det(H ′ ) could be calculated in O(r 3 ) time (Schwarzenberg-Czerny, 1995) . We could claim that the group {h g(i) } r i=1 is linearly independent if det(H ′ ) ∕ = 0, or {h g(i) } r i=1 is linear dependent if det(H ′ ) = 0.

A.9 THE PROOF OF THEOREM 7

Proof. For |∆c ij | ≤ ! 1 and |∆b j | ≤ ! 2 , there is:

!∆C! ≤ r! 1 and !∆b! ≤ √ r! 2 .

The matrix norm ! • ! here denotes the largest singular value of the matrix. Note that elements of matrix C and vector b are overlap of quantum states, which are bounded in [-1, 1], so there is:

!C! ≤ r and !b! ≤ √ r.

We have:

!∆x! = !(C + ∆C) -1 (∆b -∆C • C -1 b)! ≤ !C -1 ! • !(I + C -1 ∆C) -1 ! • (!∆b! + !∆C • C -1 b!) ≤ !C -1 ! • 1 1 -!C -1 ∆C! • (!∆b! + !∆C!!C -1 !!b!) ≤ !C -1 ! 1 -!C -1 !r! 1 • ( √ r! 2 + r 3/2 ! 1 !C -1 !) ≤ ! 2 √ r .

Thus, for u t = # r j=1 x j s j and ũt = # r j=1 xj s j , there is:

!u t -ũt ! = √ ∆x T C∆x ≤ !∆x! • !C! 1/2 ≤ ! 2 √ r • √ r = ! 2 .

A.10 THE ESTIMATION OF c ij = 〈s i |s j 〉

The overlap c ij = 〈s i |s j 〉 = 〈h g(i) |h g(j) 〉 can be estimated by the Hadamard Test. We provide the detail in Algorithm 6: Proposition 4. Algorithm 6 present the !-estimation to the overlap c ij = 〈s i |s j 〉 with probability at least 1 -δ with running time O(T H ! -2 log(1/δ)). Create state [|s i 〉|0〉 + |s j 〉|1〉]/ √ 2.

Apply the Hadmard gate on the second register to obtain the state

|si〉+|sj 〉 2 |0〉+ |si〉-|sj 〉 2

|1〉.

Measure the second register and record the result. (1 + e -θj ) 2 + (h(θ j ) -y j ) (-1) ! e θj -e -θj " e -2θj

(1 + e -θj )

4 x (k) j > x (i) j = 2x (i) j x (k) j e -2θj

(1 + e -θj ) 4 :

1 -(h(θ j ) -y j ) ! e θj -e -θj "; .

(49) Define

α j ≡ 2 e -2θj

(1 + e -θj ) 4 :

1 -(h(θ j ) -y j ) ! e θj -e -θj "; ,

we have: ∇ 2 w f j = α j x j x T j .

(51)

Thus we could derive the Hessian matrix for the total loss function:

EQUATION

Each term in the sum above is a rank-1 matrix, which means the rank of H is bounded by n. Thus, for sparse samples {x j } n j=1 with at most s non-zero elements, we could derive the Hessian as the form {(i, j, h ij |h ij ∕ = 0)} in time O(ns 2 ). Note that in practical case, d, the dimension of the sample x j , can be millions large (for example, the number of pixels on an image), while n, the number of sample involved in one iteration of the update, is relatively small.

:

g(i) is the index of the i-th column vector in the complete basis.

Figures and Tables:

6: end for 7: Count the result in step 4 and step 5 to obtain the sequence {(| λj |, n j , m j )} r j=1 . n j is the number of resulting | λj | in step 4, and m j is the number of resulting 1 in step 5 for different | λj |. 8: if mj nj < 1 2 for all j ∈ [r], then make the non-vector statement; 9: else, choose the largest | λj | which satisfies the condition mj nj > 1 2 .

4.2 COORDINATES ESTIMATION Assume the complete basis {|s 1 〉, |s 2 〉, • • • , |s r 〉} has been selected out in Section 4.1. Thus the read-out problem could be viewed as solving the equation |u t 〉 = # r i=1 x i |s i 〉, where x i ∈ R are unknown variables. The coordinate {x i } r i=1 could be obtained by solving the r-dimensional linear equation system Cx = b, where b i = 〈u t |s i 〉 and c ij = 〈s i |s j 〉 for i, j ∈ [r]. The equation Cx = b could be solved classically in at most O(r 3 ) time. Note that we can only get the approximation to c ij or b i instead of the exact value. Theorem 7 verifies the impact of the approximate error to c ij or b i on the read-out of the target state. Theorem 7. Suppose cjk is the ! 1 -approximation to c jk = 〈s j |s k 〉 and bj is the ! 2 -approximation to b j = 〈u t |s j 〉, ∀j, k ∈ [r], where ! 1 = ! 6r 2 "C -1 " 2 and ! 2 = ! 6r"C -1 " . Denote vector x ∈ R r as the solution of Cx = b. Then x could lead an approximate eigenvector ũt = # r j=1 xj s j , such that !ũ t -u t ! ≤ !/2.

(Shao, 2018)  Assume state |φ i 〉 could be prepared by given unitary operation in time T in , for i ∈ [n]. Then there is a unitary which could prepare the state |φ〉 = # n i=1 α i |φ i 〉 in time O(T in n log(n/!) ) with error !. Note that here we actually perform the state |t ′ m+1 〉 = |g(1)〉|g(2)〉 • • • |g(m + 1)〉|t m+1 〉 from states {|g(1)〉|g(2)〉 • • • |g(m + 1)〉|s i 〉} m+1 i=1 , and each state ( 2 m+1 j=1 |g(j)〉)|s i 〉 could be performed by oracle U H on state ( 2 m+1 j=1 |g(j)〉)|0〉. Denote U m+1 as the unitary which generates the state % 2 m+1 j=1 |g(j)〉 & |t m+1 〉 from the state % 2 m+1 j=1 |g(j)〉 & |0〉. The operation in step (c) of procedure (11):

Define vector y = -Z m+1 x. Note that all parameters c ij = 〈s i |s j 〉, i, j ∈ [m] and b j = 〈s m+1 |s j 〉, j ∈ [m] are estimated by Hadamard test, which takes time O(T H ! ′-2 ) with error bounded in ! ′ (see Appendix A.10 for more information). Thus the calculation on vector y = C -1 m b would have an error. Define matrix Cm = C m + ∆C m and b = b + ∆b which are estimations on C m and b. Suppose |c ij -c ij | ≤ ! 1 and | bi -b i | ≤ ! 1 are error bounds for c ij and b i , respectively, ∀i, j ∈ [m]. Denote ỹ = C-1 m b as the solution to the approximate linear equation and ∆y = ỹ -y as the error to y. We have: ' C m y = b, (C m + ∆C m )(y + ∆y) = (b + ∆b).

c ij estimation Input: Quantum access to oracle U H . The index number i and j. The precision parameter !. The probability error bound δ. Output: An estimation cij to the valuec ij = 〈s i |s j 〉, such that cij ∈ [c ij -! , c ij + !] with probability at least 1 -δ. 1: for k = 1 to n = [ 2 ! 2 log( 2 δ )] + 1 do 2:

5: end for 6: Count the number of resulting 0 in step 4 as m. Output 2m/n -1 as the estimation to c ij . be generated by performing the following procedure on state |g(i)〉|g(j)〉|0〉|0〉:|g(i)〉|g(j)〉|0〉|0〉 H -→|g(i)〉|g(j)〉|0〉 |0〉 + |1〉 √ 2 (40) U H ⊗|0〉〈0| -------→|g(i)〉|g(j)〉 |h g(i) 〉|0〉 + |0〉|1〉 √ 2 (41) U H ⊗|1〉〈1| -------→|g(i)〉|g(j)〉 |h g(i) 〉|0〉 + |h g(j) in(40) acts on the 4-th register. The gate U H ⊗ |0〉〈0| in (41) acts on the 1-st, 3-rd and 4-th registers. The gate U H ⊗ |1〉〈1| in (42) acts on the 2-nd, 3-rd and 4-th registers. A.11 THE ESTIMATION OF b i = 〈u t |s i 〉The estimation to the overlap b i = 〈u t |s i 〉 is more complicated. Technics like Algorithm 6 is infeasible, due to the post-selection method for generating target state |u t 〉. Here we 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 |ψ〉. The circuit of the Quantum Swap Test is illustrated in Figure1.

Figure 1: Circuit of the Quantum Swap Test As shown in Figure 1, Quantum Swap Test performs the operation:|0〉|φ〉|ψ〉 → (H ⊗ I)(|0〉〈0| ⊗ I + |1〉〈1| ⊗ U SW AP )(H ⊗ I)|0〉|φ〉|ψ〉. (44)The final state could be written as:1 2 |0〉(|φ〉|ψ〉 + |ψ〉|φ〉) + 1 2 |1〉(|φ〉|ψ〉 -|ψ〉|φ〉). (45)The U SW AP gate could be implemented in time O(polylog(d)), which performs the swap transformation |φ〉|ψ〉 → |ψ〉|φ〉 for d-dimensional state |φ〉 and |ψ〉. The measurement on the first qubit

So state |u t 〉 could be generated in N times of measurement with probability at least 1 -δ. By considering the time complexity to run the quantum SVE algorithm (O(T

Table content: <table/>

Alex Schwarzenberg-Czerny. 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 arXiv:1807.09693, 2018.

Table content: <table><tr><td>Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings</td></tr><tr><td>of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 217-228. ACM, 2019.</td></tr></table>

Mappings |x〉|0〉 → |P x〉 and |0〉|x〉 → |Qx〉 can be performed by the quantum oracle U H and V H respectively. Algorithm 4 Positive-Negative Eigenvalue Discrimination(PNED) Algorithm Input: Quantum access to oracles U H and V H . Eigenstate |u〉 which corresponds to eigenvalue λ. Output: A random boolean variable with distribution P (0) = 1+λ/"H" F Apply gate U H ⊗ |0〉〈0| + V H ⊗ |1〉〈1| on the state to obtain 1 Apply the Hadmard gate on the third register to obtain the state |P u〉+|Qu〉 Measure the third register and output the result. Theorem 8. Positive-negative eigenvalue discrimination. For eigenvalue λ of H with property |λ| ≥ a, one could run Algorithm 4 for n

Table content: <table><tr><td>2 2: Apply the Hadmard gate on the third register to obtain the state 1 1: Create state |u〉|0〉|0〉. √ 2 (|u〉|0〉|0〉 + |u〉|0〉|1〉). and P (1) = 1-λ/"H" F 2 3: Apply the Controlled-SWAP gate to obtain the state 1 √ 2 (|u〉|0〉|0〉 + |0〉|u〉|1〉). 4: √ 2 (|P u〉|0〉 + |Qu〉|1〉). 5: 2 |0〉 + |P u〉-|Qu〉 2 |1〉. . 6:</td></tr></table>

By Theorem 9, the implementation of state | t′ m+1 〉 = [ H (m + 1) log(2(m+1)/!3) ) with error bounds ! 3 /2. Thus, we can implement state |t′ m+1 〉 = [ 2 m+1 j=1 |g(j)〉]|t m+1 〉 by unitary in time O(m 3 + m 2 T H ! -2 1 + T H (m + 1) log(2(m+1)/!3)) with error bounds in ! 3 .

Table content: <table><tr><td>2 m+1 j=1 |g(j)〉]| tm+1 〉 takes time O(T Now we consider the influence of imperfect implementation of state | t′ m 〉 to Algorithm 3. For simplicity, we neglect the term [ 2 m j=1 |g(j)〉] in state |t ′ m 〉 = [</td></tr></table>

Peer review (iclr2020):
This paper proposes a new quantum algorithm which can efficiently estimate the eigen vectors of a Hessian matrix with negative eigenvalue. Decision I 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. Comments I 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? The section 2.2 should give a brief overview of why both techniques will be useful for the many parts of the contributed algorithms. I could not find definition of T_H anywhere.