Search

Neural network is a powerful learning paradigm for data feature learning in the era of big data. However, most neural network models are deterministic models that ignore the uncertainty of data. Fuzzy neural networks are proposed to address this problem. FDNN is a hierarchical deep neural network that derives information from both fuzzy and neural representations, the representations are then fused to form representation to be classified. FDNN perform well on uncertain data classification tasks. In this paper, we proposed a novel hierarchical fused quantum fuzzy neural network (HQFNN). Different from classical FDNN, HQFNN uses quantum neural networks to learn fuzzy membership functions in fuzzy neural network. We conducted simulated experiment on two types of datasets (Dirty-MNIST and 15-Scene), the results show that the proposed model can outperform several existing methods. In addition, we demonstrate the robustness of the proposed quantum circuit.

The Quantum Alternating Operator Ansatz (QAOA+) is one of the Variational Quantum Algorithm (VQA) specifically developed to tackle combinatorial optimization problems by exploring the feasible space in search of a target solution. For constrained optimization problems with unconstrained variables, which we call Unconstrained-Variables Problems (UVPs), the mixed operators in the QAOA+ circuit are applied to the constrained variables, while the single-qubit rotating gates $R_X$ operate on the unconstrained variables. The expressibility of this circuit is limited by the shortage of two-qubit gates and the parameter sharing in the $R_X$, which consequently impacts the performance of QAOA+ for solving UVPs. Therefore, it is crucial to develop a suitable ansatz for UVPs. In this paper, we propose the Variational Quantum Algorithm-Preserving Feasible Space (VQA-PFS) ansatz, exemplified by the Uncapacitated Facility Location Problem (UFLP), that applies mixed operators on constrained variables while employing Hardware-Efficient Ansatz (HEA) on unconstrained variables. The numerical results demonstrate that VQA-PFS significantly enhances the success probability and exhibits faster convergence compared to QAOA+, Quantum Approximation Optimization Algorithm (QAOA), and HEA. Furthermore, VQA-PFS reduces the circuit depth dramatically in comparison to QAOA+ and QAOA. Our algorithm is general and instructive in tackling UVPs.

The values of the low-energy constants (LECs) are very important in the chiral perturbation theory. This paper adopts a Bayesian method with the truncation errors to globally fit eight next-to-leading order (NLO) LECs $L_i^r$ and next-to-next-leading order (NNLO) LECs $C_i^r$. With the estimation of the truncation errors, the fitting results of $L_i^r$ in the NLO and NNLO are very close. The posterior distributions of $C_i^r$ indicate the boundary-dependent relations of these $C_i^r$. Ten $C_i^r$ are weakly dependent on the boundaries and their values are reliable. The other $C_i^r$ are required more experimental data to constrain their boundaries. Some linear combinations of $C_i^r$ are also fitted with more reliable posterior distributions. If one knows some more precise values of $C_i^r$, some other $C_i^r$ can be obtained by these values. With these fitting LECs, most observables provide a good convergence, except for the $\pi K$ scattering lengths $a_0^{3/2}$ and $a_0^{1/2}$. An example is also introduced to test the improvement of the method. All the computations indicate that considering the truncation errors can improve the global fit greatly, and more prior information can obtain better fitting results. This fitting method can be extended to the other effective field theories and the perturbation theory., Comment: 27+11 pages, 5 figures

As a general framework, Matrix Exponential Dimensionality Reduction (MEDR) deals with the small-sample-size problem that appears in linear Dimensionality Reduction (DR) algorithms. High complexity is the bottleneck in this type of DR algorithm because one has to solve a large-scale matrix exponential eigenproblem. To address it, here we design a general quantum algorithm framework for MEDR based on the block-encoding technique. This framework is configurable, that is, by selecting suitable methods to design the block-encodings of the data matrices, a series of new efficient quantum algorithms can be derived from this framework. Specifically, by constructing the block-encodings of the data matrix exponentials, we solve the eigenproblem and then obtain the digital-encoded quantum state corresponding to the compressed low-dimensional dataset, which can be directly utilized as input state for other quantum machine learning tasks to overcome the curse of dimensionality. As applications, we apply this framework to four linear DR algorithms and design their quantum algorithms, which all achieve a polynomial speedup in the dimension of the sample over their classical counterparts., Comment: 14 pages, 6 figures

Recently, Zhou et al. have proposed a novel Interpolation-based (INTERP) strategy to generate the initial parameters for the Parameterized Quantum Circuit (PQC) in Quantum Approximate Optimization Algorithm (QAOA). INTERP produces the guess of the initial parameters at level $i+1$ by applying linear interpolation to the optimized parameters at level $i$, achieving better performance than random initialization (RI). Nevertheless, INTERP consumes extensive running costs for deep QAOA because it necessitates optimization at each level of the PQC. To address this problem, a Multilevel Leapfrogging Interpolation (MLI) strategy is proposed. MLI can produce the guess of the initial parameters from level $i+1$ to $i+l$ ($l>1$) at level $i$, omitting the optimization rounds from level $i+1$ to $(i+l-1)$. The final result is that MLI executes optimization at few levels rather than each level, and this operation is referred to as Multilevel Leapfrogging optimization (M-Leap). The performance of MLI is investigated on the Maxcut problem. Compared with INTERP, MLI reduces most optimization rounds. Remarkably, the simulation results demonstrate that MLI can achieve the same quasi-optima as INTERP while consuming only 1/2 of the running costs required by INTERP. In addition, for MLI, where there is no RI except for level $1$, the greedy-MLI strategy is presented. The simulation results suggest that greedy-MLI has better stability (i.e., a higher average approximation ratio) than INTERP and MLI beyond obtaining the same quasi-optima as INTERP. According to the efficiency of finding the quasi-optima, the idea of M-Leap might be extended to other training tasks, especially those requiring numerous optimizations, such as training adaptive quantum circuits.

The Quantum Alternating Operator Ansatz (QAOA+) is an extension of the Quantum Approximate Optimization Algorithm (QAOA), where the search space is smaller in solving constrained combinatorial optimization problems. However, QAOA+ requires a trivial feasible solution as the initial state, so it cannot be used for problems that are difficult to find a trivial feasible solution. For simplicity, we call them as Non-Trivial-Feasible-Solution Problems (NTFSP). In this paper, we take the Minimum Exact Cover (MEC) problem as an example, studying how to apply QAOA+ to NTFSP. As we know, exact covering (EC) is the feasible space of MEC problem, which has no trivial solutions. To overcome the above problem, the EC problem is divided into two steps to solve. First, disjoint sets are obtained, which is equivalent to solving independent sets. Second, on this basis, the sets covering all elements (i.e., EC) are solved. In other words, we transform MEC into a multi-objective constrained optimization problem, where feasible space consists of independent sets that are easy to find. Finally, we also verify the feasibility of the algorithm from numerical experiments. Our method provides a feasible way for applying QAOA+ to NTFSP, and is expected to expand its application significantly.

Anomaly detection of sequences is a hot topic in data mining. Anomaly Detection using Piecewise Aggregate approximation in the Amplitude Domain (called ADPAAD) is one of the widely used methods in anomaly detection of sequences. The core step in the classical algorithm for performing ADPAAD is to construct an approximate representation of the subsequence, where the elements of each subsequence are divided into several subsections according to the amplitude domain and then the average of the subsections is computed. It is computationally expensive when processing large-scale sequences. In this paper, we propose a quantum algorithm for ADPAAD, which can divide the subsequence elements and compute the average in parallel. Our quantum algorithm can achieve polynomial speedups on the number of subsequences and the length of subsequences over its classical counterpart.

Mean Centering (MC) is an important data preprocessing technique, which has a wide range of applications in data mining, machine learning, and multivariate statistical analysis. When the data set is large, this process will be time-consuming. In this paper, we propose an efficient quantum MC algorithm based on the block-encoding technique, which enables the existing quantum algorithms can get rid of the assumption that the original data set has been classically mean-centered. Specifically, we first adopt the strategy that MC can be achieved by multiplying by the centering matrix $C$, i.e., removing the row means, column means and row-column means of the original data matrix $X$ can be expressed as $XC$, $CX$ and $CXC$, respectively. This allows many classical problems involving MC, such as Principal Component Analysis (PCA), to directly solve the matrix algebra problems related to $XC$, $CX$ or $CXC$. Next, we can employ the block-encoding technique to realize MC. To achieve it, we first show how to construct the block-encoding of the centering matrix $C$, and then further obtain the block-encodings of $XC$, $CX$ and $CXC$. Finally, we describe one by one how to apply our MC algorithm to PCA and other algorithms.

Discriminative Canonical Correlation Analysis (DCCA) is a powerful supervised feature extraction technique for two sets of multivariate data, which has wide applications in pattern recognition. DCCA consists of two parts: (i) mean-centering that subtracts the sample mean from the sample; (ii) solving the generalized eigenvalue problem. The cost of DCCA is expensive when dealing with a large number of high-dimensional samples. To solve this problem, here we propose a quantum DCCA algorithm. Specifically, we devise an efficient method to compute the mean of all samples, then use block-Hamiltonian simulation and quantum phase estimation to solve the generalized eigenvalue problem. Our algorithm achieves a polynomial speedup in the dimension of samples under certain conditions over its classical counterpart.

Solving eigenproblem of the Laplacian matrix of a fully connected weighted graph has wide applications in data science, machine learning, and image processing, etc. However, this is very challenging because it involves expensive matrix operations. Here, we propose an efficient quantum algorithm to solve it based on a assumption that the element of each vertex and its norms can be effectively accessed via a quantum random access memory data structure. Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework to implement the quantum simulation of the Laplacian matrix. Then, the eigenvalues and eigenvectors of the Laplacian matrix are extracted by the quantum phase estimation algorithm. The core of our entire algorithm is to construct the block-encoding of the Laplacian matrix. To achieve this, we propose in detail how to construct the block-encodings of operators containing the information of the weight matrix and the degree matrix respectively, and further obtain the block-encoding of the Laplacian matrix. Compared with its classical counterpart, our algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex. We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.

Neighborhood Preserving Embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101, 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality $n$. However, the algorithm has two disadvantages: (1) It is incomplete in the sense that the input of the third sub-algorithm cannot be obtained by the second sub-algorithm. (2) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points $m$ and an exponential speedup on the dimensionality $n$ under certain conditions over the classical NPE algorithm, and achieve significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA., Comment: 12 pages

Anomaly detection plays a critical role in fraud detection, health care, intrusion detection, military surveillance, etc. Anomaly detection algorithm based on density estimation (called ADDE algorithm) is one of widely used algorithms. Liang et al. proposed a quantum version of the ADDE algorithm [Phys. Rev. A 99, 052310 (2019)] and it is believed that the algorithm has exponential speedups on both the number and the dimension of training data point over the classical algorithm. In this paper, we find that Liang et al.'s algorithm doesn't actually execute. Then we propose a new quantum ADDE algorithm based on amplitude estimation. It is shown that our algorithm can achieves exponential speedup on the number $M$ of training data points compared with the classical counterpart. Besides, the idea of our algorithm can be applied to optimize the anomaly detection algorithm based on kernel principal component analysis (called ADKPCA algorithm). Different from the quantum ADKPCA proposed by Liu et al. [Phys. Rev. A 97, 042315 (2018)], compared with the classical counterpart, which offer exponential speedup on the dimension $d$ of data points, our algorithm achieves exponential speedup on $M$.

Unsharp measurements play an increasingly important role in quantum information theory. In this paper, we study a three-party prepare-transform-measure experiment with unsharp measurements based on $ 3 \rightarrow 1 $ sequential random access codes (RACs). We derive optimal trade-off between the two correlation witnesses in $ 3 \rightarrow 1 $ sequential quantum random access codes (QRACs), and use the result to complete the self-testing of quantum preparations, instruments and measurements for three sequential parties. We also give the upper and lower bounds of the sharpness parameter to complete the robustness analysis of the self-testing scheme. In addition, we find that classical correlation witness violation based on $3 \rightarrow 1 $ sequential RACs cannot be obtained by both correlation witnesses simultaneously. This means that if the second party uses strong unsharp measurements to overcome the classical upper bound, the third party cannot do so even with sharp measurements. Finally, we give the analysis and comparison of the random number generation efficiency under different sharpness parameters based on the determinant value, $2 \rightarrow 1 $ and $3 \rightarrow 1 $ QRACs separately. This letter sheds new light on generating random numbers among multi-party in semi-device independent framework., Comment: arXiv admin note: text overlap with arXiv:1905.06726 by other authors

Most quantum information tasks based on Bell tests relie on the assumption of measurement independence. However, it is difficult to ensure that the assumption of measurement independence is always met in experimental operations, so it is crucial to explore the effects of relaxing this assumption on Bell tests. In this paper, we discuss the effects of relaxing the assumption of measurement independence on 1-parameter family of Bell (1-PFB) tests. For both general and factorizable input distributions, we establish the relationship among measurement dependence, guessing probability, and the maximum value of 1-PFB correlation function that Eve can fake. The deterministic strategy when Eve fakes the maximum value is also given. We compare the unknown information rate of Chain inequality and 1-PFB inequality, and find the range of the parameter in which it is more difficult for Eve to fake the maximum quantum violation in 1-PFB inequality than in Chain inequality.

Dimensionality reduction (DR) algorithms, which reduce the dimensionality of a given data set while preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan \emph{et al}. proposed a quantum version of the A-optimal projection algorithm (AOP) for dimensionality reduction [Phys. Rev. A 99, 032311 (2019)] and claimed that the algorithm has exponential speedups on the dimensionality of the original feature space $n$ and the dimensionality of the reduced feature space $k$ over the classical algorithm. In this paper, we correct the time complexity of Duan \emph{et al}.'s algorithm to $O(\frac{\kappa^{4s}\sqrt{k^s}} {\epsilon^{s}}\mathrm{polylog}^s (\frac{mn}{\epsilon}))$, where $\kappa$ is the condition number of a matrix that related to the original data set, $s$ is the number of iterations, $m$ is the number of data points and $\epsilon$ is the desired precision of the output state. Since the time complexity has an exponential dependence on $s$, the quantum algorithm can only be beneficial for high dimensional problems with a small number of iterations $s$. To get a further speedup, we propose an improved quantum AOP algorithm with time complexity $O(\frac{s \kappa^6 \sqrt{k}}{\epsilon}\mathrm{polylog}(\frac{nm}{\epsilon}) + \frac{s^2 \kappa^4}{\epsilon}\mathrm{polylog}(\frac{\kappa k}{\epsilon}))$ and space complexity $O(\log_2(nk/\epsilon)+s)$. With space complexity slightly worse, our algorithm achieves at least a polynomial speedup compared to Duan \emph{et al}.'s algorithm. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when both $\kappa$, $k$ and $1/\epsilon$ are $O(\mathrm{polylog}(nm))$., Comment: 11 pages, 2 figures

Matrices with the displacement structures of circulant, Toeplitz, and Hankel types as well as matrices with structures generalizing these types are omnipresent in computations of sciences and engineering. In this paper, we present efficient and memory-reduced quantum algorithms for solving linear systems with such structures by devising a new approach to implement the block-encodings of these structured matrices. More specifically, by decomposing $n\times n$ dense matrices into linear combinations of displacement matrices, we first deduce the parameterized representations of the matrices with displacement structures so that they can be treated similarly. With such representations, we then construct $\epsilon$-approximate block-encodings of these structured matrices in two different data access models, i.e., the black-box model and the QRAM data structure model. It is shown the quantum linear system solvers based on the proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms in the black-box model and an exponential speedup in the QRAM data structure model. In particular, these linear system solvers subsume known results with significant improvements and also motivate new instances where there was no specialized quantum algorithm before. As an application, one of the quantum linear system solvers is applied to the linear prediction of time series, which justifies the claimed quantum speedup is achievable for problems of practical interest., Comment: 19 pages

Logistic regression (LR) is an important machine learning model for classification, with wide applications in text classification, image analysis and medicine diagnosis, etc. However, training LR generally entails an iterative gradient descent method, and is quite time consuming when processing big data sets. To solve this problem, we present a quantum algorithm for LR to implement the key task of the gradient descent method, obtaining the classical gradients in each iteration. It is shown that our algorithm achieves exponential speedup over its classical counterpart in each iteration when the dimension of each data point M grows polylogarithmically with the number of data points N, i.e.,M=O(polylog N). It is worth noting that the optimal model parameters are finally derived by performing simple calculations on the obtained gradients. So once the optimal model parameters are determined, one can use them to classify new data at little cost., Comment: We have just found that our core algorithm is similar to the algorithm of a published paper (Shao C. Physical Review A, 2019, 99(4): 042325.),which makes our algorithm less innovative, so we apply for retraction

The increasing availability of massive administrative datasets linking postsecondary enrollees with post-college earnings records has stimulated a wealth of new research on the returns to college, and has accelerated state and federal efforts to hold institutions accountable for students' labor market outcomes. Many of these new research and policy efforts rely on state databases limited to postsecondary enrollees who work in the same state post-college, with limited information regarding family background and pre-college ability. In this paper, we use recent waves of data from the National Longitudinal Survey of Youth 1997 (NLSY97) to provide new, nationally representative, non-experimental estimates of the returns to degrees, as well as to assess the possible limitations of single-state, administrative-data-based estimates. To do this we evaluate how the national estimates change, depending upon the baseline comparison group, adjustments for pre-college achievement and family background, and alternative ways of addressing interstate mobility. We conclude with a discussion of the relative advantages and disadvantages of survey versus administrative data for estimating returns to college, as well as implications for research and policy efforts based upon single-state administrative databases. The appendices presented here include: (1) Definitions and Additional Notes for Key Variables; (2) Additional Details of Data Cleaning; (3) Comparing Self-Reported and Administrative College Enrollment and Attainment Data; (4) Results of Crosschecking Self-Reported Survey Data and Postsecondary Transcripts Data for the NLSY97; and (5) Selected Studies on the Labor Market Returns to Postsecondary Education. [For the full report: "Estimating Returns to College Attainment: Comparing Survey and State Administrative Data Based Estimates," see ED573076.]

The increasing availability of massive administrative datasets linking postsecondary enrollees with post-college earnings records has stimulated a wealth of new research on the returns to college, and has accelerated state and federal efforts to hold institutions accountable for students' labor market outcomes. Many of these new research and policy efforts rely on state databases limited to postsecondary enrollees who work in the same state post-college, with limited information regarding family background and pre-college ability. In this paper, we use recent waves of data from the National Longitudinal Survey of Youth 1997 (NLSY97) to provide new, nationally representative, non-experimental estimates of the returns to degrees, as well as to assess the possible limitations of single-state, administrative-data-based estimates. To do this we evaluate how the national estimates change, depending upon the baseline comparison group, adjustments for pre-college achievement and family background, and alternative ways of addressing interstate mobility. We conclude with a discussion of the relative advantages and disadvantages of survey versus administrative data for estimating returns to college, as well as implications for research and policy efforts based upon single-state administrative databases. [For "Estimating Returns to College Attainment: Comparing Survey and State Administrative Data Based Estimates: Appendices A, B, C, D, and E," see ED573077.]

Ridge regression (RR) is an important machine learning technique which introduces a regularization hyperparameter $\alpha$ to ordinary multiple linear regression for analyzing data suffering from multicollinearity. In this paper, we present a quantum algorithm for RR, where the technique of parallel Hamiltonian simulation to simulate a number of Hermitian matrices in parallel is proposed and used to develop a quantum version of $K$-fold cross-validation approach, which can efficiently estimate the predictive performance of RR. Our algorithm consists of two phases: (1) using quantum $K$-fold cross-validation to efficiently determine a good $\alpha$ with which RR can achieve good predictive performance, and then (2) generating a quantum state encoding the optimal fitting parameters of RR with such $\alpha$, which can be further utilized to predict new data. Since indefinite dense Hamiltonian simulation has been adopted as a key subroutine, our algorithm can efficiently handle non-sparse data matrices. It is shown that our algorithm can achieve exponential speedup over the classical counterpart for (low-rank) data matrices with low condition numbers. But when the condition numbers of data matrices is large to be amenable to full or approximately full ranks of data matrices, only polynomial speedup can be achieved., Comment: 12 pages, 3 figures