Year: 2019

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 ( ∇2f (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 = ∇2f(x) with negative eigenvalue. This computation could take time O(d2) 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) : Rd → R which has LLipschitz continuous gradient and the corresponding Hessian , we aim to build a quantum algorithm that could efficiently provide the unit vector u with the condition:
uTHu ≤ −α+ !, (1)
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:
uTHu < −α. (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(d2). 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 xij |i〉〈j|, where xij is the i, j-th element of d × d matrix X with eigen-decomposition X = ∑rank(X) i=1 λiuiui, previous quantum PCA algorithm (Lloyd et al., 2014) could perform the
mapping ∑ j βj |uj〉 → ∑
j βj |uj〉|λ̃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}dj=1. However, this model only suits the case when λj/d is relatively large, and it would take time O(d3!−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 |ut〉 = ∑r i=1 xi|si〉, where {si}ri=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 |ut〉 (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 Õ(polylog(d)poly(r)!−1), by providing the target state |ut〉 (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 |ut〉 can be written as the linear combination form |ut〉 = ∑r i=1 xi|si〉, where {si}ri=1 is a linearly independent basis sampled from column vectors {hj}dj=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 |ut〉 = ∑r
i=1 xi|si〉 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 Õ(poly(r)!−2rc) to find an index set {g(i)}ri=1, where r is the rank of H , c = 2 log 4r‖H‖F ! and {g(i)} r i=1 forms a complete basis {|hg(i)〉}ri=1 with probability at least 3/4. Theorem 2. The classical description of the target state |ut〉 = ∑r i=1 xi|si〉 could be presented in time Õ(polylog(d)poly(r)!−5) with error bounds in !2 , when the basis set {sj} 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 yT . The notation 〈y|x〉 denotes the value yTx/(‖y‖‖x‖). The notation |y〉〈x| denotes the matrix yxT /(‖y‖‖x‖). Quantum state is unitary, which means ‖|x〉‖2 = 〈x|x〉 = 1. Thus for vector x ∈ Rd, the state |x〉 is defined as ∑d j=1 xj/‖x‖|j〉, where xj is the j-th component of vector x and {|j〉}dj=1 is the state basis which acts like {ej}dj=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〉}dj=1 could randomly produce different index j with probability x2j/‖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 ∈ Rm×n. The lowercase form hi is defined as the i-th column vector of matrix H ∈ Rd×d. xi is defined as the i-th component of vector x. The tensor product of two matrix A ∈ Rm×n and B ∈ Rp×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 |x1〉 and |x2〉 which is written as |x1〉|x2〉. We present definitions of smoothness and γ-separation here.
Definition 1. (smoothness) A function f : Rd → 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 = {a1, a2, · · · , an} is said to be γ-separated if |ai − aj | > γ, ∀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 ∈ Rd×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 λjuju 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 ∈ Rd×d, we assume that H is stored in a classical data structure such that the following quantum oracles could be implemented:
UH : |i〉|0〉 → |i〉|hi〉 = 1
‖hi‖
d∑
j=1
hij |i〉|j〉, ∀i ∈ [d], (3)
VH : |0〉|j〉 → |h̃〉|j〉 = 1
‖H‖F
d∑
i=1
‖hi‖|i〉|j〉, ∀j ∈ [d], (4)
where h̃ stands for the d-dimensional vector whose i-th component is ‖hi‖/‖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 TH as the time complexity of these oracles.
Quantum Singular Value Estimation (SVE): Given matrix H ∈ Rd×d which has the eigenvalue decomposition H = ∑r j=1 λjujuj , 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 |uj〉 → ∑ j βj |uj〉||̂λj |〉 with time complexity O(THpolylog(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 |ut〉 (for case (1)) or making the non-vector statement (for case (2)). The target state |ut〉 corresponds to the eigenvector ut which satisfies the condition uTt Hut ≤ −α+ !/2. Here we present a tighter restrict on the target state |ut〉 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 UH and VH . The parameter ! and α in the NCF problem. Output: The target state |ut〉 whose corrsponding classical unit vector ut satisfies the condition
uTt Hut ≤ −α + !/2; or a statement with high probability that there is no such kind of unit vector u which satisfies the condition uTHu ≤ −α. 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 uTHu ≤ −α. 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(TH‖H‖Fpolylog(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 ∈ Rd×d is the Hessian matrix derived from the function f : Rd → 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 |uj〉, the output state of quantum SVE algorithm has the form ∑ j βj |uj〉||λ̂j |〉. We could generate different pure state |uj〉 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(TH‖H‖5Fpolylog(d)!−1) to solve the negative curvature finding problem by providing the target state |ut〉 or making the statement that there is no unit vector satisfies the condition uTHu ≤ −α.
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 |uj〉|uj〉 for the quantum SVE model and obtain the state:
1
‖H‖F
r∑
j=1
λj |uj〉|uj〉||λ̃j |〉.
The measurement on the eigenvalue register would lead this entangled state collapse to different states |uj〉|uj〉 for j ∈ [r]. We could obtain the state |uj〉 by neglecting the state in any other register. Using state |uj〉 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 UH and VH . 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 uTHu < −α. 1: for k = 1 to 4‖H‖ 2 F
α2 (2 4‖H‖2F α2 log 1 δ + 3) do
2: Create the state 1‖H‖F ∑r
j=1 λj |uj〉|uj〉. 3: Apply the quantum SVE model to obtain the state 1‖H‖F ∑r j=1 λj |uj〉|uj〉||λ̃j |〉, where
|λ̃j | ∈ |λj | ± !/4 with probability 1− 1/poly(d). 4: Measure the eigenvalue register and mark the result. 5: Use the rest state in the first register as the input to apply the PNED algorithm. 6: end for 7: Count the result in step 4 and step 5 to obtain the sequence {(|λ̃j |, nj ,mj)}rj=1. nj is the number
of resulting |λ̃j | in step 4, and mj is the number of resulting 1 in step 5 for different |λ̃j |. 8: if mjnj < 1 2 for all j ∈ [r], then make the non-vector statement; 9: else, choose the largest |λ̃j | which satisfies the condition mjnj > 1 2 .
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 uTHu < −α, with time complexity O(TH‖H‖5Fpolylog(d)!−1).
3.3 TARGET STATE GENERATING
Suppose the result of Algorithm 2 implies the existence of the target eigenvector ut, which satisfies uTt Hut ≤ −α + !/2. Then in order to give a solution to the NCF problem, we need to obtain the vector ut. In this section we construct a quantum procedure to generate the state |ut〉. The classical read-out of |ut〉, which means to estimate vector ut from quantum state |ut〉, 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 |uj〉|uj〉 as the input of quantum SVE algorithm to obtain state:
1
‖H‖F
r∑
j=1
λj |uj〉|uj〉||λ̃j |〉.
Suppose λt denotes the eigenvalue of |ut〉 that λt ≤ −α+ !/2. The measurement on the eigenvalue register could generate state |ut〉|ut〉 with probability Pt = λ 2 t
‖H‖2F ≥ α
2
4‖H‖2F . Thus the probability
of generating at least one state |ut〉 in N = [ 4 ‖H‖2F α2 log 1 δ ] + 1 times of measurement is 1 − (1 − Pt)N . There is: 1 − (1 − Pt)N ≥ 1 − e−NPt ≥ 1 − e− log(1/δ) = 1 − δ. So state |ut〉 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(TH‖H‖Fpolylog(d)!−1)) and setting the probability error bound δ = 1/poly(d), we could derive the time complexity of generating target state in Theorem 5. The detail of Target State Generating algorithm is in Appendix (Algorithm 5).
Theorem 5. Suppose that Hessian H has the eigenvector ut with eigenvalue less than −α + !2 . Then state |ut〉 could be generated in time O(TH‖H‖3Fpolylog(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 ut from the quantum state |ut〉. Generally, the classical read-out of a d-dimensional quantum state takes at least Õ(d) times of measurement to obtain the form |x〉 = ∑d i=1 xiei. 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 |ut〉 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 |ut〉 = ∑r i=1 xi|hg(i)〉1 could be presented in time O(THpolylog(d)poly(r)!−5) with error bounds in !/2, when the complete basis set {hg(j)}rj=1 is given.
Recall that our Hessian matrix H ∈ Rd×d has the eigendecomposition H = ∑r
j=1 λjuju T j , where
λj is the eigenvalue of H with respect to eigenvector uj . Then, any eigenvector of H that corresponds to a non-zero eigenvalue could be represented as the linear combination of vectors in {hj}dj=1 because Huj = λjuj can be written as ∑d i=1 hiu (i) j = λjuj . Since H has the rank of r, there exists a subset of complete basis {hg(i)}ri=1 of the column space, which is sampled from the set {hj}dj=1. Thus, any eigenvector uj could also be represented as the linear combination of vectors in {hg(i)}ri=1.
Back to the state read-out problem, denote si as hg(i) for simplicity. Suppose the target state |ut〉 that we generated in the previous section can be written as |ut〉 = ∑r i=1 xi|si〉, where {xi}ri=1 are coordinates of the state |ut〉 under the basis {|si〉}ri=1. Thus, instead of simply reading out components of vector ut, we could get the classical description of |ut〉 by calculating each xi. Note that the complete basis {|si〉}ri=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 SI = {g(1), g(2), · · · , g(r)} from [d], which corresponds to the complete basis {|hg(i)〉}ri=1. The quantum complete basis selection algorithm can be viewed as the quantum version of Gram-Schmidt orthogonalization: firstly we choose |t1〉 = |hg(1)〉 from the set {|hj〉}dj=1; then given state set {|tm〉}lm=1, we choose |tl+1〉 ∝ |hg(l+1)〉− ∑l m=1 |tm〉〈tm|hg(l+1)〉 from the state set {|hj〉− ∑l m=1 |tm〉〈tm|hj〉}dj=1. Since the chosen |tl+1〉 is orthogonal to states {|tm〉}lm=1 for each iteration l ∈ [r−1], the state set {|tm〉}rm=1 forms an orthonormal basis. Note that the state |tm〉 is generated along with an index g(m) for m ∈ [r], so we would obtain a complete basis index set {g(m)}rm=1 after the implementation of this quantum algorithm. The quantum complete basis selection algorithm is provided in Algorithm 3, in which we denote:
|φ(l)1 〉 ≡ 1
‖H‖F
d∑
j=1
‖hj‖|j〉 {[ |hj〉 − l∑
m=1
|tm〉〈tm|hj〉 ] |0〉 − l∑
m=1
|tm〉〈tm|hj〉|1〉 } , (5)
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 {si}ri=1 are linearly independent. Theorem 6. The Algorithm 3 takes time O(THpoly(r)!−2r2 log(4r‖H‖F /!)) to find an index set {g(i)}ri=1, which forms a complete basis {|hg(i)〉}ri=1 with probability at least 3/4.
1g(i) is the index of the i-th column vector in the complete basis.
Algorithm 3 Complete Basis Selection Input: Quantum access to oracle UH and VH . Output: The index set of the complete basis: SI = {g(i)}ri=1.
1: Initialize the index set SI = ∅. 2: for l = 0 to r − 1 do 3: Create the state |φ(l)1 〉 defined in Equation (5). 4: 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〉‖hj‖ [ |hj〉 − ∑l m=1 |tm〉〈tm|hj〉 ] .
5: Measure the first register and record the result as g(l + 1). 6: Denote |tl+1〉 as the state proportional to |hg(l+1)〉 − ∑l m=1 |tm〉〈tm|hg(l+1)〉. 7: Update the index set SI = SI ∪ {g(l + 1)}. 8: end for
Lemma 2. It takes O(r3) time to check whether the vector set {si}ri=1 is linearly independent when the classical access to Hessian H is given, where si is sampled from column vectors of matrix H .
4.2 COORDINATES ESTIMATION
Assume the complete basis {|s1〉, |s2〉, · · · , |sr〉} has been selected out in Section 4.1. Thus the read-out problem could be viewed as solving the equation |ut〉 = ∑r i=1 xi|si〉, where xi ∈ R are unknown variables. The coordinate {xi}ri=1 could be obtained by solving the r-dimensional linear equation system Cx = b, where bi = 〈ut|si〉 and cij = 〈si|sj〉 for i, j ∈ [r]. The equation Cx = b could be solved classically in at most O(r3) time. Note that we can only get the approximation to cij or bi instead of the exact value. Theorem 7 verifies the impact of the approximate error to cij or bi on the read-out of the target state.
Theorem 7. Suppose c̃jk is the !1-approximation to cjk = 〈sj |sk〉 and b̃j is the !2-approximation to bj = 〈ut|sj〉, ∀j, k ∈ [r], where !1 = !6r2‖C−1‖2 and !2 = ! 6r‖C−1‖ . Denote vector x̃ ∈ R r as the solution of C̃x = b̃. Then x̃ could lead an approximate eigenvector ũt = ∑r
j=1 x̃jsj , such that ‖ũt − ut‖ ≤ !/2.
We propose several methods in Appendix to estimate overlap bi = 〈ut|si〉 and cij = 〈si|sj〉, 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 cij = 〈si|sj〉 in time O(TH!−21 ) and !2-estimation to bi = 〈ut|si〉 in time O((TInput + TH)!−42 ), where TInput is the time to generate state |ut〉. Since the time complexity to generate the target state is O(TH‖H‖3Fpolylog(d)!−1) as proposed in Theorem 5, we could derive Proposition 3.
Considering the time complexity O(TH‖H‖5Fpolylog(d)!−1) to label the proper eigenvalue and the time complexity O(THpoly(r)!−2r2 log(4r‖H‖F /!)) to generate the complete basis set, we could solve the NCF problem in time O(THpolylog(d)poly(r)!−2(!−3+ r2 log(4r‖H‖F /!))) by providing the target vector in the form ut = ∑r i=1 xihg(i)/‖hg(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(TH!−1poly(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(THpoly(r)polylog(d)!−2(!−3 + r2 log(4r‖H‖F /!))), which is exponentially faster on the degree of d than existing general quantum state read-out methods.
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 approximate 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.10415, 2019.
Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001.
Yair Carmon and John C Duchi. Gradient descent efficiently finds the cubic-regularized non-convex newton step. arXiv preprint arXiv:1612.00547, 2016.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2):1751–1772, 2018.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gé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 optimization. In Advances in 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, 51(6):1025–1041, November 2004. ISSN 0004-5411. doi: 10.1145/ 1039488.1039494. URL http://doi.acm.org/10.1145/1039488.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.04754, 2018.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pp. 409–426. Springer, 1994.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine LearningVolume 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.04811, 2019.
Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. arXiv preprint arXiv:1603.08675, 2016.
Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on learning theory, pp. 1246–1257, 2016.
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631, 2014.
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1):177–205, 2006.
Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical review letters, 113(13):130503, 2014.
Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd. Quantum singular-value decomposition of nonsparse low-rank matrices. Physical review A, 97(1):012327, 2018.
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.
Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 217–228. ACM, 2019.
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 vTHv ≤ λj ≤ max ‖v‖=1 vTHv, ∀j ∈ [d].
By the definition of the Hessian matrix, for unit vector v, we have:
Hv = ∇2f(x)v = lim h→0 ∇f(x+ hv)−∇f(x) h .
From above equation, we can obtain:
vTHv ≤ ‖v‖ · ‖Hv‖ ≤ limh→0 ‖∇f(x+hv)−∇f(x)‖h ≤ limh→0 L‖hv‖ h = L,
and vTHv ≥ −‖v‖ · ‖Hv‖ ≥ − limh→0 ‖∇f(x+hv)−∇f(x)‖h ≥ − limh→0 L‖hv‖
h = −L. Thus, the eigenvalue λj is bounded in [−L,L] for all j ∈ [d]. We have ‖H‖2F = ∑ i ∑ j h 2 ij = Tr(H ·H) = ∑ j λj(H 2) ≤ rL2 , so ‖H‖F ≤ √ rL.
Lemma 3. Hoeffding’s inequality (Hoeffding, 1994)
Suppose X1, X2, · · · , Xn are independent random variables with bounds Xi ∈ [ai, bi], ∀i ∈ [n]. Define X = 1n ∑n i=1 Xi , then ∀! > 0, we have:
P (X − E[X] ≥ !) ≤ exp (− 2n 2!2∑n
i=1(bi − ai)2 ), (6)
and
P (X − E[X] ≤ −!) ≤ exp (− 2n 2!2∑n
i=1(bi − ai)2 ). (7)
A.3 THE DETAIL ABOUT ALGORITHM 4
In Algorithm 4, P ∈ Rd2×d is the matrix whose column vector pi = ei ⊗ hi‖hi‖ for i ∈ [d] , and Q ∈ Rd2×d is the matrix whose column vector qj = h̃‖H‖F ⊗ ej for j ∈ [d]. hi is the i-th column vector of matrix H and h̃ is a d-dimensional vector whose i-th component is ‖hi‖. It can be directly obtained that the matrix P and Q satisfy the decomposition H/‖H‖F = P TQ and have property P TP = QTQ = I . Mappings |x〉|0〉 → |Px〉 and |0〉|x〉 → |Qx〉 can be performed by the quantum oracle UH and VH respectively.
Algorithm 4 Positive-Negative Eigenvalue Discrimination(PNED) Algorithm Input: Quantum access to oracles UH and VH . Eigenstate |u〉 which corresponds to eigenvalue λ. Output: A random boolean variable with distribution P (0) = 1+λ/‖H‖F2 and P (1) = 1−λ/‖H‖F 2 .
1: Create state |u〉|0〉|0〉. 2: Apply the Hadmard gate on the third register to obtain the state 1√
2 (|u〉|0〉|0〉+ |u〉|0〉|1〉).
3: Apply the Controlled-SWAP gate to obtain the state 1√ 2 (|u〉|0〉|0〉+ |0〉|u〉|1〉). 4: Apply gate UH ⊗ |0〉〈0|+ VH ⊗ |1〉〈1| on the state to obtain 1√2 (|Pu〉|0〉+ |Qu〉|1〉). 5: Apply the Hadmard gate on the third register to obtain the state |Pu〉+|Qu〉2 |0〉+ |Pu〉−|Qu〉 2 |1〉. 6: 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 = 2[‖H‖ 2 F
a2 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:
P (1) = ‖ |Pu〉 − |Qu〉 2 ‖2 = 1 4 (〈Pu|− 〈Qu|)(|Pu〉 − |Qu〉). (8)
Note that 〈Pu|Qu〉 = uTP TQu = 1‖H‖F u THu = λ‖H‖F , so P (1) = 1−λ/‖H‖F 2 . Similarly we have P (0) = 1+λ/‖H‖F2 .
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 Xi such that P (Xi = 1) = p and P (Xi = 0) = 1 − p and Sn = ∑n i=1 Xi. Then there has the Hoeffding’s inequality P (Sn/n− p ≤ −!) ≤ e−2n! 2 and P (Sn/n− p ≥ !) ≤ e−2n! 2 .
Back to the problem, suppose λ < 0, by setting n = 2x + 1, n(p − !) = x and P = 1−λ/‖H‖F2 , we have:
P (S2x+1 ≤ x) ≤ exp(−2(2x+ 1)[ 1− λ/‖H‖F 2 − x 2x+ 1 ]2) < e − 2x+12 λ2 ‖H‖2 F ≤ e − 2x+12 a2 ‖H‖2 F .
Similarly for λ > 0, there is P (S2x+1 ≥ x) ≤ e − 2x+12
a2
‖H‖2 F .
Let e − 2x+12
a2
‖H‖2 F ≤ δ , we have x ≥ [‖H‖ 2 F
a2 log 1 δ − 1 2 ] + 1.
A.4 THE PROOF OF THEOREM 4
Proof. The input state 1‖H‖F ∑r j=1 λj |uj〉|uj〉 could be generated with oracles UH and VH :
|0〉|0〉 VH−→ 1‖H‖F
d∑
i=1
‖hi‖|i〉|0〉 UH−→ 1‖H‖F
d∑
i=1
d∑
j=1
hij |i〉|j〉. (9)
Since H has the eigen-decomposition H = ∑r
k=1 λkuku T k , we could rewrite entry hij as
hij = ∑r k=1 λku (i) k u (j) k , where u (i) k is the i-th component of vector uk. Thus the state
1 ‖H‖F ∑d i=1 ∑d j=1 hij |i〉|j〉 could be written as:
1
‖H‖F
d∑
i=1
d∑
j=1
r∑
k=1
λku (i) k u (j) k |i〉|j〉 =
1
‖H‖F
r∑
k=1
λk|uk〉|uk〉.
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(TH‖H‖Fpolylog(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 nt = 2[
‖H‖2F λ2t log 1δ − 1 2 ] + 3
numbers of state |ut〉 in order to guarantee that λt < 0 with probability 1 − δ. Note that the probability of generating state |ut〉 in each iteration of step 2-4 in Algorithm 2 is Pt = λ 2 t
‖H‖2F .
So averagely we need to perform step 2-4 in Algorithm 2 for n = ‖H‖ 2 F λ2t {2[‖H‖ 2 F λ2t log 1δ − 1 2 ] + 3} times. The number n can be roughly upper bounded by 4‖H‖ 2 F
α2 (2 4‖H‖2F α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(TH‖H‖Fpolylog(d)!−1)) and setting the probability error bound δ = 1/poly(d), we could derive that the time complexity of Algorithm 2 is O(TH‖H‖5Fpolylog(d)!−1).
A.5 TARGET STATE GENERATING ALGORITHM
Algorithm 5 Target State Generating Input: Quantum access to oracles UH and VH . Parameters α and ! in the NCF problem. Output: The target state |ut〉 with property 〈ut|H|ut〉 = λt ≤ −α+ !/2.
1: for k = 1 to [ 4 ‖H‖2F α2 log 1 δ ] + 1 do 2: Create the state 1‖H‖F ∑r
j=1 λj |uj〉|uj〉. 3: Apply the quantum SVE model to obtain the state 1‖H‖F ∑r j=1 λj |uj〉|uj〉||λ̃j |〉, where
|λ̃j | ∈ |λj | ± !/4 with probability 1− 1/poly(d). 4: Measure the eigenvalue register and mark the result. 5: 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. 7: end if 8: end for
A.6 THE DETAIL ABOUT ALGORITHM 3
Consider the state:
  l∏
j=1
|g(j)〉

⊗|φ(l)1 〉 ≡ 1
‖H‖F
[ l∏
j=1
|g(j)〉 ] d∑
j=1
‖hj‖|j〉 {[ |hj〉 − l∑
m=1
|tm〉〈tm|hj〉 ] |0〉 − l∑
m=1
|tm〉〈tm|hj〉|1〉 } ,
(10)
we note that the state |φ(l)1 〉 in Step 3 of Algorithm 3 can be generated by the following procedure: [ l∏
j=1
|g(j)〉 ] |0〉|0〉 (a)−−→ 1‖H‖F [ l∏
j=1
|g(j)〉 ] d∑
j=1
‖hj‖|j〉|hj〉 (11)
(b)−−→ 1‖H‖F
[ l∏
j=1
|g(j)〉 ] d∑
j=1
‖hj‖|j〉|hj〉 |0〉+ |1〉√
2 (12)
(c)−−→ 1‖H‖F
[ l∏
j=1
|g(j)〉 ] d∑
j=1
‖hj‖|j〉 {[ |hj〉 − 2 l∑
m=1
|tm〉〈tm|hj〉 ] |0〉√ 2 + |hj〉 |1〉√ 2
}
(13)
(d)−−→ 1‖H‖F
[ l∏
j=1
|g(j)〉 ] d∑
j=1
‖hj‖|j〉 {[ |hj〉 − l∑
m=1
|tm〉〈tm|hj〉 ] |0〉 − l∑
m=1
|tm〉〈tm|hj〉|1〉 }
(14)
(e)−−→ 1‖H‖F
d∑
j=1
‖hj‖|j〉 {[ |hj〉 − l∑
m=1
|tm〉〈tm|hj〉 ] |0〉 − l∑
m=1
|tm〉〈tm|hj〉|1〉 } .
(15)
In step (a), we employ the quantum oracles UHVH on ancillas |0〉|0〉. In step (b), an auxiliary register |0〉 is appended, followed by a Hadamard gate. In step (c), we apply operation ∏l m=1[Rm⊗ |0〉〈0|+ I ⊗ |1〉〈1|]. The operation Rm is defined on the register |g(1)〉, · · · |g(m)〉, |hj〉:
Rm = I ⊗(m+1) − 2
{[ m∏
j=1
|g(j)〉 ] |tm〉
}{[ m∏
j=1
〈g(j)| ] 〈tm| } .
In step (d), we apply the Hadamard gate on the auxiliary register. In step (e), we trace out registers∏l j=1 |g(j)〉 to generate state |φ (l) 1 〉.
The crucial part in Algorithm 3 is to implement the reflection Rm. For the m+ 1 case, there is:
|tm+1〉 = 1
Zm+1 (|sm+1〉 −
m∑
i=1
|ti〉〈ti|sm+1〉), (16)
Note that {|ti〉} forms the orthogonal basis: 〈ti|tj〉 = 0, ∀i ∕= j, and Zm+1 = 〈tm+1|sm+1〉 = ‖|sm+1〉 − ∑m i=1 |ti〉〈ti|sm+1〉‖ = √ 1− ∑m i=1〈ti|sm+1〉2. Denote |ti〉 ≡ ∑i
j=1 xij |sj〉. The restriction that |tm+1〉 is normalized and orthogonal to states |s1〉, |s2〉, · · · |sm〉 could yield Equation (17):


m+1∑
i=1
xm+1,i〈sj |si〉 = 0, ∀j ∈ [m],
m+1∑
j=1
m+1∑
i=1
xm+1,jxm+1,i〈sj |si〉 = 1. (17)
Note that xm+1,m+1 = 1/Zm+1 by Equation (16). Define the m-dimensional vectors x, b, and the m×m matrix Cm to be:
x =
m∑
i=1
xm+1,iei , b =
m∑
j=1
〈sj |sm+1〉ej ,Cm = {cij ≡ 〈si|sj〉}m,mi,j ,
where each value cij = 〈si|sj〉 could be estimated by Hadamard Test. Thus, we could derive the following linear equations about x from Equation (17):
 

Cmx = − 1
Zm+1 b,
xT b = Z2m+1 − 1 Zm+1 .
(18)
We could obtain the coordinate {xm+1,i}m+1i=1 by solving Equation (18). There is:
 

xm+1,m+1 = 1
Zm+1 =
√ |Cm|
|Cm+1| ,
xm+1,i = − 1
Zm+1 |C(i)m | |Cm| , ∀i ∈ [m],
(19)
where matrix C(i)m 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+1
i=1 xm+1,i|si〉. Thus, we could construct a unitary to generate the state [∏m+1 j=1 |g(j)〉 ] |tm+1〉 from the state[∏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〉 = 1Zc (x|a〉 + y|b〉). The method is based on the fact that R2θ = (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 SPAN{|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〉√ x2+y2+2xy〈a|b〉
. The linear sum of 2 states could be generalized to n case:
Theorem 9. (Shao, 2018) Assume state |φi〉 could be prepared by given unitary operation in time Tin, for i ∈ [n]. Then there is a unitary which could prepare the state |φ〉 = ∑n i=1 αi|φi〉 in time O(Tinnlog(n/!)) with error !.
Note that here we actually perform the state |t′m+1〉 = |g(1)〉|g(2)〉 · · · |g(m + 1)〉|tm+1〉 from states {|g(1)〉|g(2)〉 · · · |g(m + 1)〉|si〉}m+1i=1 , and each state ( ∏m+1 j=1 |g(j)〉)|si〉 could be performed by oracle UH on state ( ∏m+1
j=1 |g(j)〉)|0〉. Denote Um+1 as the unitary which generates the state [∏m+1 j=1 |g(j)〉 ] |tm+1〉 from the state [∏m+1 j=1 |g(j)〉 ] |0〉. The operation in step (c) of procedure (11): ∏l
m=1[Rm ⊗ |0〉〈0| + I ⊗ |1〉〈1|] could be performed by∏l m=1 {[ U†m+1(I − 2|0〉〈0|)Um+1 ] ⊗ |0〉〈0|+ I ⊗ |1〉〈1| } .
A.7 THE PROOF OF THEOREM 6
Denote Pl 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/Pl) times. The Lemma 4 provides a lower bound on Pl.
Lemma 4. The probability of resulting 0 after the measurement in Step 4 of Algorithm 3 as the lower bound Pl ≥ (r−l)! 2
4‖H‖2F .
Proof. Suppose λ21 ≥ λ22 ≥ · · · ≥ λ2r , where λi is the eigenvalue of H . Since state |tm〉 is the linear sum of {|hj〉}dj=1, we can assume that |tm〉 has the decomposition |tm〉 = ∑r i=1 wmi|ui〉, for all
m = 1, 2, · · · , l, where ∑r
i=1 wmiwni = δmn. There is:
Pl = 1
‖H‖2F
d∑
j=1
[ ‖hj‖2‖|hj〉 − l∑
m=1
|tm〉〈tm|hj〉‖2 ]
= 1
‖H‖2F
d∑
j=1
[ ‖hj‖2 − l∑
m=1
‖hj‖2|〈tm|hj〉|2 ]
= 1− 1‖H‖2F
d∑
j=1
l∑
m=1
[ r∑
i=1
wmiλiu (j) i
]2
= 1− 1‖H‖2F
d∑
j=1
l∑
m=1
  r∑
i=1
w2miλ 2 i (u (j) i ) 2 +
r∑ i ∕=k wmiwmkλiλku (j) i u (j) k


= 1− 1‖H‖2F
l∑
m=1
r∑
i=1
w2miλ 2 i
= 1− 1‖H‖2F
r∑
i=1
ciλ 2 i ,
where ci = ∑l m=1 w 2 mi. Consider the r-dimensional vector wm = ∑r
i=1 wmiei. The vector set {wm}lm=1 forms an orthogonal basis in a l-dimensional subspace. Note that we can add wl+1, · · ·wr such that {wm}rm=1 forms an orthonormal basis in the whole r-dimensional space. Denote matrix W = (w1,w2, · · · ,wr). Since WTW = I . Since W is unitary, there is:
r∑
m=1
w2mi = 1, ∀i ∈ [r]. (20)
Thus we have the upper bound: ci = ∑l m=1 w 2 mi ≤ ∑r m=1 w 2 mi = 1. Note that ∑r i=1 ci =∑r
i=1 ∑l m=1 w 2 mi = ∑l m=1 ∑r i=1 w 2 mi = l, so there is:
Pl ≥ 1− 1
‖H‖2F
l∑
i=1
λ2i =
∑r i=l+1 λ 2 i
‖H‖2F . (21)
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 Pl ≥ (r−l)! 2
4‖H‖2F .
The error of implementing |tm+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.
Define vector y = −Zm+1x. Note that all parameters cij = 〈si|sj〉, i, j ∈ [m] and bj = 〈sm+1|sj〉, j ∈ [m] are estimated by Hadamard test, which takes time O(TH!′−2) with error bounded in !′ (see Appendix A.10 for more information). Thus the calculation on vector y = C−1m b would have an error. Define matrix C̃m = Cm +∆Cm and b̃ = b+∆b which are estimations on Cm and b. Suppose |c̃ij − cij | ≤ !1 and |b̃i − bi| ≤ !1 are error bounds for cij and bi, respectively, ∀i, j ∈ [m]. Denote ỹ = C̃−1m b as the solution to the approximate linear equation and ∆y = ỹ − y as the error to y. We have:
{ Cmy = b,
(Cm +∆Cm)(y +∆y) = (b+∆b).
So there is:
‖∆y‖ = ‖(Cm +∆Cm)−1(∆b−∆Cm ·C−1m b)‖ ≤ ‖C−1m ‖ · ‖(I +C−1m ∆Cm)−1‖ · (‖∆b‖+ ‖∆Cm ·C−1m b‖)
≤ ‖C−1m ‖ · 1 1− ‖C−1m ∆Cm‖ · (‖∆b‖+ ‖∆Cm‖‖C−1m ‖‖b‖) ≤ ‖C −1 m ‖
1− ‖C−1m ‖m!1 · ( √ m!1 +m 3/2!1‖C−1m ‖) ≤ 2m3/2‖C−1m ‖2!1 1− ‖C−1m ‖m!1 .
The norm ‖C−1m ‖ here denotes the largest norm of eigenvalues of matrix C−1m . Thus, for !2 = 3m3/2‖C−1m ‖2!1, we have bound ‖∆y‖ ≤ !2. For |tm+1〉 = ∑m+1 i=1 xm+1,i|si〉 and |t̃m+1〉 = ∑m+1 i=1 x̃m+1,i|si〉, there is:
〈tm+1|t̃m+1〉 = m+1∑
i=1
m+1∑
j=1
xm+1,icij x̃m+1,j = 1
Zm+1Z̃m+1 [
m,m∑
i=1,j=1
yicij ỹj − m∑
i=1
yibi − m∑
j=1
bj ỹj + 1]
= 1
Zm+1Z̃m+1 [1−
m∑
i=1
yibi] = Zm+1
Z̃m+1 .
Note that the form |t̃m+1〉 = ∑m+1 i=1 x̃m+1,i|si〉 is not a normalized state:
‖|t̃m+1〉‖2 = m+1∑
i=1
m+1∑
j=1
x̃m+1,icij x̃m+1,j = 1
Z̃2m+1 [
m,m∑
i=1,j=1
ỹicij ỹj + 1− 2 m∑
i=1
ỹibi]
= 1
Z̃2m+1 [
m,m∑
i=1,j=1
∆yicij∆yj + 2
m,m∑
i=1,j=1
∆yicijyj +
m,m∑
i=1,j=1
yicijyj + 1− 2 m∑
i=1
∆yibi − 2 m∑
i=1
yibi]
= 1
Z̃2m+1 [Z2m+1 +
m,m∑
i=1,j=1
∆yicij∆yj ].
Thus, the overlap between state |tm+1〉 and |t̃m+1〉 is:
〈tm+1|t̃m+1〉 ‖|t̃m+1〉‖ = Zm+1√
Z2m+1 +∆y TCm∆y
. (22)
There is:
‖|tm+1〉 − |t̃m+1〉/‖|t̃m+1〉‖‖ = √√√√2− 2
Zm+1√ Z2m+1 +∆y TCm∆y (23)
≤ √√√√2− 2
Zm+1√ Z2m+1 + ‖∆y‖2‖Cm‖
(24)
≤ √ 2− 2 Zm+1
Zm+1 + ‖Cm‖‖∆y‖2
2Zm+1
(25)
≤ ‖Cm‖ 1/2‖∆y‖
Zm+1 (26)
≤ m 1/2!2
Zm+1 = 3m2‖C−1m ‖2!1 Zm+1 . (27)
Let !3/2 = 3m2‖C−1m ‖ 2!1 Zm+1
. It is clear that to obtain the linear combination form |t̃m+1〉 =∑m+1 i=1 x̃m+1,i|si〉 takes time O(m3 + m2TH! −2 1 ), where ‖|t̃m+1〉/‖|t̃m+1〉‖ − |tm+1〉‖ ≤
!3/2. By Theorem 9, the implementation of state |t̃′m+1〉 = [ ∏m+1
j=1 |g(j)〉]|t̃m+1〉 takes time O(TH(m + 1)log(2(m+1)/!3)) with error bounds !3/2. Thus, we can implement state |t′m+1〉 = [ ∏m+1
j=1 |g(j)〉]|tm+1〉 by unitary in time O(m3+m2TH! −2 1 +TH(m+1) log(2(m+1)/!3)) with error bounds in !3.
Now we consider the influence of imperfect implementation of state |t̃′m〉 to Algorithm 3. For simplicity, we neglect the term [ ∏m j=1 |g(j)〉] in state |t′m〉 = [
∏m j=1 |g(j)〉]|tm〉. Denote Πl =∏l
i=1(I − 2|ti〉〈ti|) and Π̃l = ∏l
i=1(I − 2|t̃i〉〈t̃i|). There is ‖Πl − Π̃l‖ ≤ 2l!3. Note that the state
|φ(l)1 〉 = 1
‖H‖F
d∑
j=1
‖hj‖|j〉 {[ |hj〉 − l∑
m=1
|tm〉〈tm|hj〉 ] |0〉 − l∑
m=1
|tm〉〈tm|hj〉|1〉 }
in step 3 of Algorithm 3 can be written as:
1
‖H‖F
d∑
j=1
‖hj‖|j〉[ Πl + I
2 |hj〉|0〉+ Πl − I 2 |hj〉|1〉].
The probability of generating 0 after the measurement on the last register is:
Pl = 1
‖H‖2F
d∑
j=1
‖hj‖2‖ Πl + I
2 |hj〉‖2.
Similarly we define |φ̃(l)1 〉 = 1‖H‖F ∑d j=1 ‖hj‖|j〉[ Π̃l+I 2 |hj〉|0〉+ Π̃l−I 2 |hj〉|1〉], and P̃l = 1‖H‖F ∑d j=1 ‖hj‖2‖ Π̃l+I 2 |hj〉‖ 2 for the approximate case.
Since the objective of step 5 is to obtain the index g(l + 1) such that the column state |hg(l+1)〉 = |sl+1〉 is linearly independent from basis {|si〉}li=1, we define P false l as the probability of selecting out the state |sl+1〉 ∈ {|si〉}li=1 in the approximate case. Note that for state |hj〉 ∈ {|si〉}li=1, (Πl + I)|hj〉 = 0, so there is:
P falsel = 1
P̃l
1
‖H‖2F
∑
j:|hj〉∈{|si〉}li=1
‖hj‖2‖ Π̃l + I
2 |hj〉‖2
=
∑ j:|hj〉∈{|si〉}li=1 ‖hj‖2‖ Π̃l+I2 |hj〉‖ 2
∑d j=1 ‖hj‖2‖ Π̃l+I 2 |hj〉‖2
=
∑ j:|hj〉∈{|si〉}li=1 ‖hj‖2‖ Π̃l−Πl2 |hj〉‖ 2
∑d j=1 ‖hj‖2(1/2 + 〈hj |Π̃l −Πl|hj〉/2 + 〈hj |Πl|hj〉/2)
≤ l 2!23 Pl − l!3 ≤ l 2!23 (r−l)!2 4‖H‖2F − l!3 .
Let !3 = ! 2
8(r−1)‖H‖2F , there is:
r−1∑
l=0
P falsel ≤ r−1∑
l=0
l2!23 2(r − 1)(r − l)!3 − l!3 ≤ r−1∑
l=0
l!3 = r(r − 1)
2
!2
8(r − 1)‖H‖2F =
r!2
16‖H‖2F ≤ 1 4 .
(28)
Thus, by choosing !3 = ! 2
8(r−1)‖H‖2F , Algorithm 3 could select out a complete basis {|si〉}ri=1 with
probability at least 34 .
Note that in Algorithm 3 we need to perform operations Ri = I − 2|t′i〉〈t′i| for i = 1, 2, · · · , r − 1, which needs the information of parameters {cij}r−1,r−1i=1,j=1 . In order to guarantee the success probability of Algorithm 3 (Equation (28)), the estimation on each cij = 〈si|sj〉 should have error bound !1 = minm∈[r−2]
Zm+1 6m2‖C−1m ‖2 !3 ≥ minm∈[r−1] Zm 48r3‖C−1r ‖2‖H‖2F !2. Thus, the estimation on each cij
takes time O(THr6‖H‖4F !−4) and the estimation on the parameter group {cij} r−1,r−1 i=1,j=1 takes time O(THr8‖H‖4F !−4). In order to obtain the description |tm〉 = ∑m
i=1 xm,i|si〉, additional time is required for solving (m-1)-dimensional equations for m = 2, 3, · · · r − 1, which results the time complexity O(r4) in total. With given parameters {xm,i}mi=1, the implementation of operation Rm = I − 2|t′m〉〈t′m| takes time O(TH(m+ 1)log(2(m+1)/!3)) ≤ O(TH · r2 log(4r‖H‖F /!)). Denote Tbasis as the required time to implement Algorithm 3 and TRi as the required time to implement operation Ri. Since in each iteration of l ∈ [r − 1], Algorithm 3 refers operation R1, R2, · · · , Rl for 1/Pl times, there is:
O(Tbasis) = O(THr8‖H‖4F !−4) + r−1∑
l=0
1
Pl
l∑
m=1
O(TRi)
≤ O(THr8‖H‖4F !−4) + 4‖H‖2F
!2 O(THr2 log(4r‖H‖F /!))
r−1∑
l=0
l
r − l
= O(TH‖H‖2F !−2(r8‖H‖2F !−2 + r1+2 log(4r‖H‖F /!))) ≤ O(THpoly(r)!−2r2 log(4r‖H‖F /!)).
A.8 THE PROOF OF LEMMA 2
Proof. Define the index function g : [r] → [d] such that si = hg(i), ∀i ∈ [r]. Consider the eigendecomposition of matrix H:
H =
r∑
j=1
λjuju T j . (29)
It is natural to generate the decomposition:
hj =
r∑
i=1
λiuiu (j) i , (30)
hjk =
r∑
i=1
λiu (j) i u (k) i . (31)
Define the r × r dimensional matrix C = (hTg(1),hTg(2), · · · ,hTg(r))T (hg(1),hg(2), · · · ,hg(r)). There is:
{hg(i)}ri=1 is linear independent ⇔ det(C) ∕= 0. (32)
Denote the jk-th element of C as cjk. Since cjk = hTj hk = ∑r i=1 λ 2 iu (j) i u (k) i , there is:
det(C) = ∣∣∣∣∣∣∣ ∑r i=1 λ 2 iu (g(1)) i u (g(1)) i · · · ∑r i=1 λ 2 iu (g(1)) i u (g(r)) i ... . . .
...∑r i=1 λ 2 iu (g(r)) i u (g(1)) i · · · ∑r i=1 λ 2 iu (g(r)) i u (g(r)) i
∣∣∣∣∣∣∣ (33)
=
r∑
i1=1
r∑
i2=1
· · · r∑
ir=1 ∣∣∣∣∣∣∣∣ λ2i1u (g(1)) i1 u (g(1)) i1 · · · λ2iru (g(1)) ir u (g(r)) ir ... . . . ... λ2i1u (g(r)) i1 u (g(1)) i1 · · · λ2iru (g(r)) ir u (g(r)) ir ∣∣∣∣∣∣∣∣ (34)
=
r∑
i1=1
r∑
i2=1
· · · r∑
ir=1
(
r∏
j=1
λ2ij )(
r∏
j=1
u (g(j)) ij ) ∣∣∣∣∣∣∣∣ u (g(1)) i1 · · · u(g(1))ir ... . . . ...
u (g(r)) i1 · · · u(g(r))ir
∣∣∣∣∣∣∣∣ . (35)
On the other hand, construct the matrix H ′ whose jk-th element is h′jk = hg(j),g(k). There is:
det(H ′) = ∣∣∣∣∣∣∣ ∑r i=1 λiu (g(1)) i u (g(1)) i · · · ∑r i=1 λiu (g(1)) i u (g(r)) i ... . . .
...∑r i=1 λiu (g(r)) i u (g(1)) i · · · ∑r i=1 λiu (g(r)) i u (g(r)) i
∣∣∣∣∣∣∣ (36)
=
r∑
i1=1
r∑
i2=1
· · · r∑
ir=1 ∣∣∣∣∣∣∣∣ λi1u (g(1)) i1 u (g(1)) i1 · · · λiru (g(1)) ir u (g(r)) ir ... . . . ... λi1u (g(r)) i1 u (g(1)) i1 · · · λiru (g(r)) ir u (g(r)) ir ∣∣∣∣∣∣∣∣ (37)
=
r∑
i1=1
r∑
i2=1
· · · r∑
ir=1
(
r∏
j=1
λij )(
r∏
j=1
u (g(j)) ij ) ∣∣∣∣∣∣∣∣ u (g(1)) i1 · · · u(g(1))ir ... . . . ...
u (g(r)) i1 · · · u(g(r))ir
∣∣∣∣∣∣∣∣ . (38)
Note that the determinant in eq(35) and eq(38) is non-zero only if im ∕= in for any different m,n ∈ [r]. Consider the summation of ij for all j ∈ [r] over {1, 2, · · · , r}, there is:
det(C)/
r∏
i=1
λ2i = det(H ′)/
r∏
i=1
λi (39)
Thus the problem about whether group {hg(i)}ri=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(r3) time (Schwarzenberg-Czerny, 1995). We could claim that the group {hg(i)}ri=1 is linearly independent if det(H ′) ∕= 0, or {hg(i)}ri=1 is linear dependent if det(H ′) = 0.
A.9 THE PROOF OF THEOREM 7
Proof. For |∆cij | ≤ !1 and |∆bj | ≤ !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−1b)‖ ≤ ‖C−1‖ · ‖(I +C−1∆C)−1‖ · (‖∆b‖+ ‖∆C ·C−1b‖)
≤ ‖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 ut = ∑r j=1 xjsj and ũt = ∑r j=1 x̃jsj , there is:
‖ut − ũt‖ = √ ∆xTC∆x ≤ ‖∆x‖ · ‖C‖1/2 ≤ ! 2 √ r · √ r = ! 2 .
A.10 THE ESTIMATION OF cij = 〈si|sj〉
The overlap cij = 〈si|sj〉 = 〈hg(i)|hg(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 cij = 〈si|sj〉 with probability at least 1− δ with running time O(TH!−2 log(1/δ)).
Algorithm 6 cij estimation Input: Quantum access to oracle UH . The index number i and j. The precision parameter !. The
probability error bound δ. Output: An estimation c̃ij to the value cij = 〈si|sj〉, such that c̃ij ∈ [cij − ! , cij + !] with
probability at least 1− δ. 1: for k = 1 to n = [ 2!2 log( 2 δ )] + 1 do
2: Create state [|si〉|0〉+ |sj〉|1〉]/ √ 2. 3: Apply the Hadmard gate on the second register to obtain the state |si〉+|sj〉2 |0〉+ |si〉−|sj〉
2 |1〉. 4: Measure the second register and record the result. 5: end for 6: Count the number of resulting 0 in step 4 as m. Output 2m/n− 1 as the estimation to cij .
State |si〉|0〉+|sj〉|1〉√ 2 = |hg(i)〉|0〉+|hg(j)〉|1〉√ 2 in step 2 could 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)
UH⊗|0〉〈0|−−−−−−−→|g(i)〉|g(j)〉 |hg(i)〉|0〉+ |0〉|1〉√
2 (41)
UH⊗|1〉〈1|−−−−−−−→|g(i)〉|g(j)〉 |hg(i)〉|0〉+ |hg(j)〉|1〉√
2 (42)
trace out the first two registers−−−−−−−−−−−−−−−→ |hg(i)〉|0〉+ |hg(j)〉|1〉√
2 . (43)
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 bi = 〈ut|si〉
The estimation to the overlap bi = 〈ut|si〉 is more complicated. Technics like Algorithm 6 is infeasible, due to the post-selection method for generating target state |ut〉. 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 Figure 1.
As shown in Figure 1, Quantum Swap Test performs the operation:
|0〉|φ〉|ψ〉 → (H ⊗ I)(|0〉〈0|⊗ I + |1〉〈1|⊗ USWAP )(H ⊗ I)|0〉|φ〉|ψ〉. (44) The final state could be written as:
1 2 |0〉(|φ〉|ψ〉+ |ψ〉|φ〉) + 1 2 |1〉(|φ〉|ψ〉 − |ψ〉|φ〉). (45)
The USWAP 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
produces 0 with probability P0 = 12 (1 + |〈φ|ψ〉| 2). 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.
Proposition 5. There exists a quantum algorithm which could present !-estimation to value b2i = |〈ut|si〉|2 with probability at least 1− δ in running time O(TInputpolylog(d)!−2 log(1/δ)), where TInput is the time complexity to generate states |ut〉 and |si〉.
In order to estimate values bi = 〈ut|si〉 for i ∈ [r], we need to discriminate the positive and negative of bi. Note that for state |ut〉, the state |−ut〉 is also a target state which shares the same eigenvalue. So both states |ut〉 and |−ut〉 are legal outputs and indistinguishable for our algorithm in Section 3. Thus we analysis the value bi = sgn(u (k) t )〈ut|si〉 as the overlap between states |ut〉 and |si〉, where u (k) t is the k-th component of vector ut. Generally k could be any index such that the corresponding component is non-zero.
Note that bi = sgn(u (k) t )〈ut|si〉 = −sgn(〈ut|hk〉)〈ut|si〉. Define two states |ψ+〉 = 1Z+ (|hk〉 + |hg(i)〉) and |ψ−〉 = 1Z− (|hk〉 − |hg(i)〉), where Z± are normalized constants such that Z 2 ± = 2± 2〈hk|hg(i)〉. Then there is:
|〈ut|ψ+〉|2 = 1
Z2+
[ 〈ut|hk〉2 + 〈ut|hg(i)〉2 + 2〈ut|hk〉〈ut|hg(i)〉 ] , (46)
|〈ut|ψ−〉|2 = 1
Z2−
[ 〈ut|hk〉2 + 〈ut|hg(i)〉2 − 2〈ut|hk〉〈ut|hg(i)〉 ] . (47)
States |ψ+〉 and |ψ−〉 could be generated by step 2-4 in Algorithm 6. The overlap 〈hk|hg(i)〉 could be estimated by Algorithm 6. The square overlap |〈ut|ψ+〉|2 and |〈ut|ψ−〉|2 could be estimated by Quantum Swap Test. Thus for |〈ut|hg(i)〉| > !′, one could discriminate the positive and negative of 〈ut|hk〉〈ut|hg(i)〉 by calculate the value Z2+|〈ut|ψ+〉|2 − Z2−|〈ut|ψ−〉|2. The estimation on the square overlap |〈ut|ψ+〉|2 and |〈ut|ψ−〉|2 need to have the precision !′|〈ut|hk〉|/2, which takes time O(TInput!′−2). For |〈ut|hg(i)〉| ≤ !′, 0 is an !′ estimation to 〈ut|hg(i)〉. Since an !′-estimation to |bi| could be achieved by an !′2-estimation to b2i which takes time O(TInput!′−4), we could derive the time complexity of estimating bi in Theorem 10.
Theorem 10. There exists a quantum algorithm which could present !-estimation to value bi = sgn(u
(k) t )〈ut|si〉 with probability at least 1−δ in running time O(TInputpolylog(d)!−4 log(1/δ)),
where TInput is the time complexity to generate states |ut〉 and |si〉.
A.12 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 = {(xj , yj)|j ∈ [n]} ⊂ Rd × {0, 1}. Consider the non-convex loss function with form: F (x,w) = [h(θ)− y]2, where h : R→ R is the non-linear function such that h(θ) = 1
1+e−θ and θ = w⊤x + b. Denote x(i)j as the ith component of xj . The total loss function
on the set S is defined as f(w) = 1n ∑n j=1 F (xj ,w) = 1 n ∑n j=1 fj(w).
There is:
∂fj ∂w(i) = 2(h(θj)− yj) ∂h(θj) ∂w(i)
= 2(h(θj)− yj) e−θj
(1 + e−θj ) 2
∂θj ∂w(i)
= 2(h(θj)− yj) e−θj
(1 + e−θj ) 2x
(i) j
(48)
∂2fj ∂w(i)∂w(k) = 2 ∂ ∂w(k)
[ (h(θj)− yj)
e−θj
(1 + e−θj ) 2
] x (i) j
= 2
[ ∂(h(θj)− yj)
∂w(k) e−θj (1 + e−θj ) 2 + (h(θj)− yj) ∂ ∂w(k) e−θj (1 + e−θj ) 2
] x (i) j
= 2
[ e−θj
(1 + e−θj ) 2x
(k) j
e−θj
(1 + e−θj ) 2 + (h(θj)− yj)
(−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)− yj) ( eθj − e−θj )] .
(49)
Define
αj ≡ 2 e−2θj
(1 + e−θj ) 4
[ 1− (h(θj)− yj) ( eθj − e−θj )] , (50)
we have: ∇2wfj = αjxjxTj . (51)
Thus we could derive the Hessian matrix for the total loss function:
H = 1
n
n∑
j=1
∇2wfj = 1
n
n∑
j=1
αjxjx T j . (52)
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 {xj}nj=1 with at most s non-zero elements, we could derive the Hessian as the form {(i, j, hij |hij ∕= 0)} in time O(ns2). Note that in practical case, d, the dimension of the sample xj , 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.

Review summaries:
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.