Quantum Divide-and-Conquer Anchoring for Separable Non-negative Matrix Factorization

1 Introduction

Non-negative matrix factorization (NMF) [Lee and Seung, 1999; Pauca et al., 2004] is popular in computer vision and machine learning, because the underlying non-negativity constraints on the two low-rank factors usually yield sparse representations of the given non-negative matrix. It has proven that NMF is NP-complete [Vavasis, 2009]. Thus, the separability assumption has been introduced [Donoho and Stodden, 2004] to NMF and induces SNMF. This assumption enables not only polynomial-time algorithms [Zhou et al., 2013; Recht et al., 2012; Van Buskirk et al., 2017], but also a geometric interpretation [Donoho and Stodden, 2004].

∗ {yudu5543@uni.,tongliang.liu@,dacheng.tao@}sydney.edu.au

† {Yinan.Li@student.,Runyao.Duan@}uts.edu.au

However, the rapid progress of the Internet technology, and the computational power and storage, as well as the wide distribute of sensors, grows data exponentially, which challenges many polynomial machine learning algorithms [Lin, 2007; Liu et al., 2017; You et al., 2017; Wang et al., 2017]. Thanks to quantum physics, quantum computing machinery and quantum machine learning are arising [Biamonte et al., 2017]. Many encouraging results have been reported recently, such as quantum support vector machine [Rebentrost et al., 2014] and quantum perceptron [Kapoor et al., 2016], which dramatically reduce the runtime complexity and achieve a more efficient learning ability.

Through exploiting quantum advantages, a logarithmic runtime complexity of SNMF is desired and then many emergent applications can be beneficial from this acceleration. Thus, we need to consider restrictions in quantum computing and answer the following questions: (1) how to convert the classical SNMF problem to accord with a quantum framework; (2) how to exploit quantum advantages, preferring to achieve the exponential speedup; and (3) how to circumvent reading out bottleneck in measurements [Aaronson, 2015].

We select the divide-and-conquer anchoring (DCA) [Zhou et al., 2013] scheme and devise quantum DCA (QDCA) for SNMF, because DCA only contains linear operations in the time-consuming divide step and this characteristic echoes with the nature of quantum computing. This answers the first question and confirms the second question by guaranteeing the exponential speedup for operations in a quantum machine.

Thanks to that indexes of anchors can be sampled with a high probability from a probability distribution in the resulting quantum states, we propose an efficient heuristic post-selection method instead of reading out all the quantum data directly (reading is an expensive operation, especially for high-dimensional vectors). This heuristic post-selection method answers the third question and ensures us to achieve the quantum speedup after measurements.

The exponential speedup for computations in quantum machine and that for transmitting indexes of anchors from quantum machine to classical computer after measurements together guarantee that the runtime complexity of QDCA achieves O(poly log(n + m)), where n × m is the size of the input non-negative matrix.

In addition, we deliver an important message through this paper. QDCA is the first algorithm that seamlessly integrates quantum and classical computations with the exponential speedup. Such kind of integration forms a general strategy to develop algorithms with quantum advantages.

The rest of this paper is organized as follows: Section 2 reviews SNMF and DCA; Section 3 elaborates QDCA and analyzes the runtime complexity; and Section 4 concludes the paper and discusses the future works.

2 Background

NMF aims to approximate a non-negative matrix X ∈ Rn×m + by the product of two nonnegative low rank factors (a basis matrix W ∈ Rn×r + and an encoding matrix H ∈ Rm×r + ), i.e., X ≈ WH⊤, where r = O(log (n + m)) ≪ min{n, m}, via solving the following optimization problem

2.1 Separable Non-negative Matrix Factorization

Solving the original NMF problem (equation (1)) is in general NP-complete [Vavasis, 2009]. Thus it is computationally intractable to obtain the global optimum in polynomial time with respect to the input size. To circumvent this difficulty, [Donoho and Stodden, 2004] introduced the separability assumption to the non-negative matrix X, i.e., X can be decomposed into X = FX(R, :), where the basis matrix X(R, :) is composited by r rows from X and F is the non-negative encoding matrix.

We denote R = {k1, k2, ..., kr}, where ki ∈ {1, 2, ..., n} and |R| = r. If a cone can be defined as cone(X(R, :)) = ∑ri=1 αiX(ki, :), αi ∈ R+, the cone(X(R, :)) is the conical hull of X(R, :). We say X is separable if ∀ki ∈ {1, ..., n}, we have

where all the data points in X are covered in a finitely generated and pointed cone(X(R, :)).

By adding an extra constraint ∑ri=1 αi = 1, we say the simplex ∆(X(R, :)) is the convex hull of X(R, :). This is valuable in practice. The selected rows in X(R, :) are called anchors (or extreme rows) of X. The non-anchor vectors in X, which are the rest n - r points in Rm+ , lie in the convex hull or conical hull, generated by the anchors and thus can be non-negatively and linearly expressed by the anchors. Figure 1 shows the geometrical interpretation of convex hull. Likewise, for the near-separable case, all data points are in or around the conical hull of the extreme rows. The concept of near-separable NMF can be straightforwardly defined by X = FX(R, :) + N, where N is a noise matrix for convenient reconstruction.

2.2 Divide-and-Conquer Anchoring

Based on a divide-and-conquer scheme that exploits the geometric information of convex hull or conical hull partially preserved in their projections, divide-and-conquer anchoring (DCA) [Zhou et al., 2013] selects the indexes of anchors from a number of operations in a low-dimensional space, for example the 1-dimensional space used in the rest of the paper. DCA is comprised of two parts: (1) the divide step, targeting the collection of indexes of anchors in the 1-dimensional space, and (2) the conquer step, aiming to determine R via collecting all (for separable case) or high frequency (for near-separable case) indexes of anchors in the 1-dimensional space. To better understand the proposed QDCA, we detail the procedure of DCA.

Divide step. Given a set of unit vectors B = {βi}si=1 ∈ Rm×s randomly sampled from the unit hypersphere Sm-1 , where s = O(r log r), we project X onto βi and obtain

Denote the indexes of the smallest and the largest entries of Yi in the 1-dimensional space as ¯ Ai , i.e.,

where i = {1, . . . , s}. As illustrated in Figure 1, each ¯ Ai corresponds to a particular pair of anchors in the original high dimensional space.

Conquer step. Under the separability assumption, we find r distinct indexes to identify all the anchors for X. Under the near-separability assumption, the indexes of anchors in randomly projected spaces are collected by selecting the most r frequently appeared indexes from { ¯ Ai }si=1 . The selection rule is defined as

where |H| is the size of the set H, and I(i ∈ ¯ Aj ) : i → {0, 1} is the indicator function for the event that an index i is within ¯ Aj of the j-th random projection operation.

3 QuantumDivide-and-Conquer Anchoring

Devising QDCA is challenging and so non-trivial. To realize quantum advantages for solving SNMF, we shall transform the DCA scheme. For simplicity, we decompose DCA into s sub-problems corresponding to s random projections, in which the i-th sub-problem is comprised of the i-th random projection and the subsequent procedure for determining ¯ Ai . It is worth noting that, in QDCA, for preserving the exponential speedup, only the index of an anchor with the maximum absolute value is collected in ¯ Ai , i.e., ¯ Ai = argmaxkj {|X(kj, :)βi|}. The random projection can be completed by an efficient quantum algorithm for linear operations [Lloyd et al., 2014], achieving an exponential speedup with respect to the classical counterpart. After the random projections, the resulting vectors will be presented as quantum states (proportional to Xβi), which are infeasible to readout all its probability amplitudes in a logarithmic runtime. To overcome this barrier and target exponential speedup, we devise a heuristic post-selection method to obtain { ¯ Ai }si=1 . In the conquer step, we employ equation (5) in classical computing. Figure 2 shows the diagram of QDCA.

Prior to detail the proposed QDCA, we introduce the notations, which are necessary to explain our results. The Dirac notations are used to follow the convention. Basically, we use |ψ〉 ∈ Hd, a normalized d-dimensional vector, to denote a d-dimensional pure quantum state in the underlying state (Hilbert) space Hd. We use 〈ψ| to denote the conjugate transpose of |ψ〉, i.e., |ψ〉 = 〈ψ† |. The standard inner product of |ψ〉 and |φ〉 is denoted as 〈ψ|φ〉. For a quantum system with Hamiltonian H (a hermitian matrix, satisfying H† = H), the unitary time evolution is characterized by the matrix exponential, e-iHt := ∑∞k=0 1 k! (-iH)k tk , where t is the simulation time. To simulate a quantum system, we are required to implement a quantum circuit which mimics the time evolution e-iHt at any time t. The spectral decomposition of H is denoted by ∑j λj |uj〉〈uj|, where λj and uj are the eigenvalue and the corresponding eigenvector of H, respectively. Specifically, the matrix exponential eH admits the form ∑j eλj |uj〉〈uj|. By default, we have |0〉 = [1 0]⊤ and |1〉 = [0 1]⊤. For n-qubits, let |i〉 be the computational basis, where |i〉 ∈ {|0〉 , |1〉}⊗n and ⊗ stands for the operation of tensor product. Detailed basic notations and preliminaries for quantum computation are referring to [Nielsen and Chuang, 2002].

Algorithm 1 summarizes the proposed QDCA algorithm. Here, we discuss its runtime complexity. In this paper, we focus on the dependence of runtime complexity on the parameters m and n, which are dimensions of the input matrix. In total s sub-problems, for the random projection operations, there exists a quantum algorithm which runs in time O(poly log(m+n)), achieving the exponential speedup with respect to classical counterparts (see Subsections 3.1 and 3.2). Indexes of anchors in projected spaces ¯ Ai for i = {1, ..., s} will be obtained by a newly designed heuristic post-selection method.

Under a plausible assumption, we prove that O(poly log(m + n)) runtime is sufficient to locate the s indexes corresponding to the largest absolute amplitude of resulting quantum states with a high probability, which constructs { ¯ Ai }si=1 and maintains the exponential speedup achieved in the previous steps. However, we have not pro-

Algorithm 1: QDCA

Input : X ∈ Rn×m + via oracle access (see Subsection 3.1);

s = O(log(m + n)) ∈ R+

k = O(poly log(n + m)) ∈ R+.

Output: The indexes of anchors R. 1 if m ̸= n or X is not hermitian then

3 end

• 4 Generating random vectors {βi}si=1 and preparing corresponding quantum states {|βi〉}si=1 (see Subsection 3.1);
• 5 Preparing a quantum circuit to simulate the unitary time evolution of e-iXt (see Subsection 3.1);
• 6 for i < s do
• 7 Applying the quantum algorithm for linear operations to produce k copies of |ψi〉:
• 8 |ψi〉 ∝ Xβi (see Subsection 3.2);
• 9 Measuring k copies of |ψi〉 using the computational basis (see Subsection 3.3);
• 10 Setting ¯ Ai = {l}, where l is the outcome that appears most frequently in quantum measurements 11 (see Subsection 3.3);

12 end

• 13 Constructing R by { ¯ Ai }si=1 , R ← arg maxH⊆[n+m],|H|=r ∑i∈H ∑sj=1 I(i ∈ ¯ Aj ) (see Subsection 3.4);

vided a rigorous runtime analysis for the worst case without any assumption, which is an interesting open problem. In the conquer step (Subsection 3.4), a classical sorting algorithm is employed, which runs in time O(s log s), where s = O(r log r) and r = O(log (n+m)). This implies that the conquer step can be completed with a runtime far less than O(poly log(m+ n)). Under the plausible assumption, the overall runtime of QDCA is O(ploy log (m+n)).

In the following subsections, we detail the QDCA. Subsection 3.1 introduces how to read classical data into quantum computer. To complete the divide step under a logarithmic runtime, Subsections 3.2 and 3.3 sequentially demonstrate how to employ the quantum algorithm for linear operations to realize random projections and how to devise heuristic postselection for transmitting. Finally, Subsection 3.4 shows that applying a classical sorting algorithm in the conquer step preserves the logarithmic runtime in QDCA.

3.1 Quantum Simulation

For the sake of exploiting quantum advantages, we first describe how to encode the given classical data matrix and random vectors into quantum states.

Without loss of generality, the input of the SNMF problem is a data matrix ˜X ∈ Rn×m with rank( ˜X) ≪ min{n,m}. In the rest of the paper, we focus on the general case, where m ̸= n. Referring to [Harrow et al., 2009], for satisfying the quantum computing requirement, we should embed ˜X into a high-dimensional matrix by employing the "extend matrix", i.e.,

which is square and hermitian. Naturally, if we can locate the anchors of X, we can then easily obtain the anchors of ˜X.

Given a low-rank hermitian matrix X ∈ R(n+m)×(n+m) , there exists an oracle, which can efficiently access the elements of X by either performing an efficient computation of the matrix elements or authorizing access to a storage medium for the elements such as quantum RAM [Giovannetti et al., 2008]. With the oracle access to X, we could prepare a quantum circuit which simulates the unitary time evolution e-iXt for a simulation time t, following the method introduced in [Berry et al., 2007; Harrow et al., 2009].

Note that, for an efficient quantum simulation, the input matrix is required to be sparse. Thus, to simulate a dense matrix X that may be encountered in SNMF, we refer to the method introduced in [Rebentrost et al., 2016; Rebentrost et al., 2018]. Specifically, X can be efficiently embedded into a large sparse matrix SX ∈ R(n+m)2×(n+m)2 . Since SX is sparse, we can use SX to conduct an efficient quantum simulation. This "modified swap matrix" SX is defined as

where Xi,j is the (i, j)-th entry of X. It is easy to see that SX is one-sparse, at which the number of non-zero elements in each column and in each row is one.

We show that, applying the simulated unitary time evolution e-iXt/(n+m) to the target state σ, is equivalent to applying e-iSXt on ρ⊗σ, where the ancillary state ρ = |⃗1〉 〈⃗1| and |⃗1〉 = 1 √n+m ∑i |i〉. Since 1/(n +m) is only a scale factor that does not influence the final result, e-iXt can therefore be efficiently simulated in quantum computer. We can trace out the ancillary state ρ from the quantum simulation system e-iSX∆tρ ⊗ σ by

This indicates that for small time ∆t, evolving with the modified swap matrix SX on the large system ρ ⊗ σ is equivalent to evolving with X/(n + m) on the σ system with a negligible error. Then generalizing to any simulation t, we can slice t into multiple ∆t. And in each ∆t, a copy of ρ is required. With an efficient oracle access to the matrix elements, we can simulate sparse matrix SX with a constant number of oracle calls and a negligible error [Berry et al., 2007; Harrow et al., 2009].

Random vectors used in DCA will be prepared as quantum states according to [Grover and Rudolph, 2002; Harrow et al., 2009]. Specifically, for a normalized vector β = [α0, · · · , α(n+m)-1]⊤ ∈ R(n+m) , if all of the entries as well as ∑i2 i=i1 |αi|2 are efficiently computable, where i2 > i1 are any numbers in {1, · · · , n + m}, we can prepare the state |β〉 = ∑n+m i=1 αi |i〉 efficiently.

Concluding remark 1. In the state preparation step, given an oracle access to the elements of a low-rank and normalized rows hermitian matrix X ∈ R(n+m)×(n+m) , there exists a quantum algorithm [Berry et al., 2007; Harrow et al., 2009] which simulates the unitary time evolution e-iXt/(n+m) in runtime O(poly log (n+m)). Likewise, given an oracle access to the elements of classical random and normalized vectors {βi}si=1 , we can efficiently prepare corresponding quantum states {|βi〉}si=1 under a logarithmic runtime.

3.2 QuantumAlgorithm for Linear Operations

After classical data are read into quantum forms, we shall utilize quantum principal component analysis scheme (QPCA) [Lloyd et al., 2014] and its subsequent phase estimation algorithm [Shor, 1999] to obtain a quantum state |ψi〉 which is proportional to random projections Xβi, for i = {1, . . . , s}.

Let the eigen-decomposition of X be ∑j λj |uj〉〈uj|, where λj and |uj〉 stand for eigenvalues and their corresponding eigenvectors. Specifically, for the dense matrix case, with the oracle Λq(·), the exponential matrix e-iXt0/(n+m) with simulation time t0 is applied to |βi〉, resulting in

where q is a positive integer, |k〉 is composed with q qubits (i.e., |k〉 = |0〉⊗q ) and the oracle Λq(·) applies k times of e-iXt0 onto |βi〉.

Next, taking |k〉 as the eigenvalue register with quantum operations, we can obtain the quantum state

where αj = 〈uj |βi〉 in time O(1/ϵ).

To obtain the analogous quantum form X |βi〉 = ∑j λj 〈uj|βi〉 |uj〉, that corresponds to the result of the random projection Xβi, the eigenvalues will be extracted into probability amplitudes of the resulting quantum state. We then follow the procedure in [Harrow et al., 2009]. Specifically, through introducing an ancilla qubit, applying rotating condition on |λj〉, and uncomputing the eigenvalue register, the resulting quantum state is proportional to

where C = O(1/λmax) and λmax is the largest eigenvalue of X.

Measuring the last qubit, conditioned on seeing 1 [Rebentrost et al., 2016], the final output state is proportional to Xβi, i.e.,

Concluding remark 2. Given the quantum circuit that simulates eiSXt and a quantum state |βi〉 encoding the vector βi, there exists a quantum algorithm for linear operations that outputs a quantum state |ψi〉, c.f., equation (9), which is proportional to the vector Xβi, in time ˜O(1/ϵ). Combined with the quantum circuit and the state preparation step in Subsection 3.1, the total runtime complexity of computing Xβi for i = {1, . . . , s} is O(poly log(n + m)/ϵ). Let the desired error be 1/ϵ = O(poly log(n+m)), the runtime complexity is O(poly log(n+m)).

3.3 Heuristic Post-Selection

The resulting quantum state |ψi〉, which is proportional to the vector Xβi, is used to determine ¯ Ai . The method to extract the expected index is non-trivial. In DCA, as the resulting vector is given explicitly after a random projection, we can pick up the indexes with the largest and the smallest entries in time O(n+m). In the quantum setting, the entries of Xβi are encoded into the probability amplitudes of |ψi〉. Reading out all probability amplitudes is exponential expensive. Even employing efficient tomography methods, such as compressed sensing [Gross et al., 2010] or sample optimal tomography [Haah et al., 2017], the runtime complexity is ˜O(n + m). Such a large cost breaks the exponential speedup achieved in the random projection step.

For the purpose of preserving the quantum advantages, we devise an alternative heuristic method to obtain ¯ Ai . The heuristic post-selection is to find the index of an anchor in the projected space (corresponding to the maximum probability amplitude of |ψi〉) under a logarithmic runtime by consuming N copies of |ψi〉. Given N copies of |ψi〉, the procedure to perform the heuristic post-selection is

1. measuring each copy |ψi〉 by the computational basis ;
2. recording the most appearing index among the N outputs as the index of an anchor in the projected space.

The quantum state |ψi〉 contains (n + m) superposition states which correspond to (n+m) indexes, i.e., the possible measurement outcomes are {1, . . . , n+m} and the probability of obtaining the index k (k ∈ {1, . . . , n+m}) is given by pk = | 〈k|ψi〉 |2 . Among the N outputs, the most frequently appearing index corresponds to the index with the largest absolute amplitude with a high probability, which is also the index of an anchor in the projected space. Note that the work [Yu et al., 2016] has proved that collecting largest absolute amplitude can also find all anchors.

The probability of finding the index of an anchor is proportional to the number of quantum state copies |ψi〉, where the index corresponds to the maximum absolute amplitude of the quantum state |ψi〉. Then, a natural question is how many copies are sufficient to determine the index of an anchor in the projected space with a high probability. The number of quantum state copies influences the runtime complexity of a quantum algorithm. Namely, using the computational basis to measure one copy of quantum state requires runtime complexity O(1), and the measurement runtime by the computational basis is proportional to the number of copies. In the following, we show that, under a plausible assumption, only N = O(poly log(n + m)) copies of |ψi〉 are sufficient to determine the index of an anchor in the projected space with a high probability.

Theorem 1. Let D be a multinomial distribution. If x ∼ D, we assume P(x = i) = pi, i ∈ {1, · · · ,N}, and ∑Ni=1 pi = 1. Let x1, · · · , xN be examples independently sampled from D and Ni be the number of examples taking value of i. Let pmax = max{p1, · · · , pN} and psecmax = max{p1, · · · , pN} \ pmax. If pmax - psecmax > 2√2 log (4N/δ)/N, then, for any δ > 0, with a probability at least 1 - δ, we have

In Theorem 1, we have a plausible assumption pmax - psecmax > 2√2 log (4N/δ)/N, which is easy to satisfy in practice. To achieve the exponential speedup, we could set N = log2 (n+m) and then we have pmax - psecmax > 2√2 log (4 log2 (n +m)/δ)/log2 (n +m), which will converge to zero as N goes to infinity. This implies that given the above plausible assumption, by using the proposed heuristic post-selection method, we could find the measured index corresponding to the maximum absolute amplitude of the resulting quantum state with a high probability. Here, the measured index also corresponds to the index of an anchor in the projected space. Recall that measuring O(poly log(n +m)) quantum state copies by the computational basis implements heuristic post-selection method.

The proof of Theorem 1 is based upon the following Breteganolle-Huber-Carol inequality [Van Der Vaart and Wellner, 1996]:

Theorem 2 (Breteganolle-Huber-Carol inequality). Let D be a multinomial distribution with l events probabilities p1, · · · , pl. Let Ni be the number of event i sampled from randomly sampled N events. Then, for any δ > 0, the following inequality holds

Proof of Theorem 1. By utilizing the Breteganolle-HuberCarol inequality, for any j ∈ {1, · · · ,N}, and δ > 0, we have

Let δ = 4 exp ( -Nλ2 2 ). The above inequality implies that for any given j ∈ {1, · · · ,N}, with probability at least 1-δ, we have

By using the union bound of probability, we have that for any δ > 0 and any j ∈ {1, · · · , N}, with probability at least 1-δ, for the following inequality holds

Since pmax-psecmax > 2√2 log (4N/δ)/N, it can be easily verified that, with a probability at least 1-δ, there is only one value Nj/N that is in the √2 log (4N/δ)/N-neighborhood of pj. We therefore conclude that argmaxi{Ni|1 ≤ i ≤ N} = arg maxi{pi|1 ≤ i ≤ N}. ■

We also conduct experiments to test the case without the plausible assumption. We empirically find that, the O(poly log (n+m)) measurements are sufficient to locate the index with the largest absolute amplitude at a very high probability. Given limited page length, we do not detail the procedure of the experiment. In a nutshell, we first generate the synthetic data in accordance with [Zhou et al., 2013]. And then, we convert the result of each random projection into a probability distribution. Afterwards, the Monte Carlo simulation is introduced to sample examples from the distribution [Binder et al., 1993]. Finally, the statistical results indicate that, with the sample size O(poly log(n + m)), the index with the largest entry can be located with a high probability.

After measuring polynomial logarithmic N copies by the computational basis with runtime O(poly log(n + m)), the most appearing index should be recorded among N outputs, which can be obtained by a classical searching algorithm. The ¯ Ai then be determined with the runtime O(poly log(n + m)). After applying the heuristic post-selection onto s subproblems, the { ¯ Ai }si=1 will be obtained. This achieves the divide step of QDCA. It is worth noting that, different to the classical DCA, QDCA only obtains the index with the largest absolute entry value. Therefore, the number of random vectors βi should be doubled. Since s ≪ min(n,m), we have 2s ≪ n + m and s is still O(r log r).

Concluding remark 3. Supported by Theorem 1, when the data size is (n +m), O(poly log(n +m)) random samples measured by computational basis are sufficient to locate the index of an anchor in a projected space with a high probability. Adding the runtime to search the most frequently appeared index, the runtime of this step is O(poly log(n+m)).

3.4 The Classical Conquer Step

Via the heuristic post-selection method, { ¯ Ai }si=1 are collected in the classical form. As analysis in Theorem 1, nonanchors may be collected with probability at most δ. Therefore, equation (5) is applied to determine the indexes of anchors. This part is completed by a classical sorting algorithm. Through employing the sorting algorithm [Knuth, 1998], s indexes of { ¯ Ai }si=1 can be sorted in time O(s log s). Since s = O(r log r), the runtime complexity is O(poly log(n + m)). After sorting, top r indexes are selected as R, which are most frequently appeared indexes in all s sub-problems. With the selected R, the decomposed matrix X(R, :) is obtained.

Concluding remark 4. Through employing the sorting algorithm on { ¯ Ai }si=1 , the indexes of anchors are obtained with runtime complexity O(poly log(n + m)).

4 Conclusion

This paper presents QDCA to dramatically reduce the runtime to achieve the exponential speedup for extracting partbased representations from a large-scale matrix. Analogous to DCA, QDCA can also solve near-separable non-negative matrix factorization problem with the exponential speedup. Moreover, the strategy of combining quantum and classical computations paves a new way to develop quantum machine learning algorithms. Through employing heuristic post-selection method, the quantum advantage is achieved after reading out quantum data into the classical form. In the future, we plan to apply this QDCA scheme to various machine learning algorithms to achieve the quantum speedup.

Acknowledgments

This research is supported by ARC projects FL-170100117 and DP-180103424.