Learning low-dimensional representation is a crucial issue for many machine-learning tasks, such as pattern recognition and image retrieval. In this article, we present a quantum algorithm and a quantum circuit to efficiently perform A-optimal projection for dimensionality reduction. Compared with the best-know classical algorithms, the quantum A-optimal projection (QAOP) algorithm shows an exponential speedup in both the original feature space dimension $n$ and the reduced feature space dimension $k$. We show that the space and time complexity of the QAOP circuit are $O[{log}_{2}(nk/\ensuremath{\epsilon})]$ and $O[{log}_{2}(nk)\text{poly}({log}_{2}{\ensuremath{\epsilon}}^{\ensuremath{-}1})],$ respectively, with fidelity at least $1\ensuremath{-}\ensuremath{\epsilon}$. First, a reformation of the original QAOP algorithm is proposed to help omit the quantum-classical interactions during the QAOP algorithm. Then the quantum algorithm and quantum circuit with performance guarantees are proposed. Specifically, the quantum circuit modules for preparing the initial quantum state and implementing the controlled rotation can be also used for other quantum machine-learning algorithms.
Learning low-dimensional representation is a crucial issue for many machine-learning tasks, such as pattern recognition and image retrieval. In this article, we present a quantum algorithm and a quantum circuit to efficiently perform A-optimal projection for dimensionality reduction. Compared with the best-know classical algorithms, the quantum A-optimal projection (QAOP) algorithm shows an exponential speedup in both the original feature space dimension n and the reduced feature space dimension k. We show that the space and time complexity of the QAOP circuit are O[log2(nk/\ensuremathϵ)] and O[log2(nk)poly(log2\ensuremathϵ\ensuremath−1)], respectively, with fidelity at least 1\ensuremath−\ensuremathϵ. First, a reformation of the original QAOP algorithm is proposed to help omit the quantum-classical interactions during the QAOP algorithm. Then the quantum algorithm and quantum circuit with performance guarantees are proposed. Specifically, the quantum circuit modules for preparing the initial quantum state and implementing the controlled rotation can be also used for other quantum machine-learning algorithms.
Dimensionality reduction algorithms, which reduce the dimensionality of a given data set whereas preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan 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 the algorithm of Duan et al. to $O\left[\frac{{\ensuremath{\kappa}}^{4s}\sqrt{{k}^{s}}}{{\ensuremath{\epsilon}}^{s}}{\mathrm{polylog}}^{s}\left(\frac{mn}{\ensuremath{\epsilon}}\right)\right]$, where $\ensuremath{\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 $\ensuremath{\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\left[\frac{s{\ensuremath{\kappa}}^{6}\sqrt{k}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{nm}{\ensuremath{\epsilon}}\right)+\frac{{s}^{2}{\ensuremath{\kappa}}^{4}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{\ensuremath{\kappa}k}{\ensuremath{\epsilon}}\right)\right]$ and space complexity $O[{log}_{2}(nk/\ensuremath{\epsilon})+s]$. With space complexity slightly worse, our algorithm achieves, at least, a polynomial speedup compared to the algorithm of Duan et al.. Also, our algorithm shows exponential speedups in n and m compared with the classical algorithm when $\ensuremath{\kappa},\phantom{\rule{0.28em}{0ex}}k$, and $1/\ensuremath{\epsilon}$ are O[polylog(nm)].
Quantum computing is a new and advanced topic that refers to calculations based on the principles of quantum mechanics. It makes certain kinds of problems be solved easier compared to classical computers. This advantage of quantum computing can be used to implement many existing problems in different fields incredibly effectively. One important field that quantum computing has shown great results in machine learning. Until now, many different quantum algorithms have been presented to perform different machine learning approaches. In some special cases, the execution time of these quantum algorithms will be reduced exponentially compared to the classical ones. But at the same time, with increasing data volume and computation time, taking care of systems to prevent unwanted interactions with the environment can be a daunting task and since these algorithms work on machine learning problems, which usually includes big data, their implementation is very costly in terms of quantum resources. Here, in this paper, we have proposed an approach to reduce the cost of quantum circuits and to optimize quantum machine learning circuits in particular. To reduce the number of resources used, in this paper an approach including different optimization algorithms is considered. Our approach is used to optimize quantum machine learning algorithms for big data. In this case, the optimized circuits run quantum machine learning algorithms in less time than the original ones and by preserving the original functionality. Our approach improves the number of quantum gates by 10.7% and 14.9% in different circuits respectively. This is the amount of reduction for one iteration of a given sub-circuit U in the main circuit. For cases where this sub-circuit is repeated more times in the main circuit, the optimization rate is increased. Therefore, by applying the proposed method to circuits with big data, both cost and performance are improved.
The application of near-term quantum devices to machine learning (ML) has attracted much attention. Recently, Mitarai et al. [Phys. Rev. A 98, 032309 (2018)] proposed a framework to use a quantum circuit for ML tasks, called quantum circuit learning (QCL). Due to the use of a quantum circuit, QCL employs an exponentially high-dimensional Hilbert space as its feature space. However, its efficiency compared to classical algorithms remains unexplored. Here, we present a classical ML algorithm that uses the same Hilbert space. In numerical simulations, our algorithm demonstrates similar performance to QCL for several ML tasks, providing a perspective for the computational and memory efficiency of quantum ML algorithms.
The application of near-term quantum devices to machine learning (ML) has attracted much attention. In one such attempt, Mitarai et al. (2018) proposed a framework to use a quantum circuit for supervised ML tasks, which is called quantum circuit learning (QCL). Due to the use of a quantum circuit, QCL can employ an exponentially high-dimensional Hilbert space as its feature space. However, its efficiency compared to classical algorithms remains unexplored. In this study, using a statistical technique called count sketch, we propose a classical ML algorithm that uses the same Hilbert space. In numerical simulations, our proposed algorithm demonstrates similar performance to QCL for several ML tasks. This provides a new perspective with which to consider the computational and memory efficiency of quantum ML algorithms.
The convergence of machine learning (ML) and quantum computing is quickly becoming a game-changing new frontier in computational science. The most intriguing area of overlap may be quantum optimization, which seeks to reduce the exponentially increasing complexity and computational cost of ML algorithms. As they grow larger and more complicated, traditional optimization methods, particularly in high-dimensional and non-convex space, will inevitably hit performance limits. Quantum optimization is the whole new paradigm that leverages quantum mechanical effects like superposition, entanglement, and tunnelling to explore solution spaces more efficiently. The chapter outlines the theory, practice, and potential of hybrid quantum-classical optimization algorithms for machine learning. The most brilliant research direction in the current NISQ (noisy intermediate-scale quantum) era is mixed systems leveraging classical computing capability augmented by quantum capacity. In such designs, computationally intensive subroutines like optimization for global optima or escape from local minima are left to quantum processors and data preprocessing, iterative refinement, and model testing are performed by classical processors. We start by defining the fundamental principles of quantum computing and acquainting readers with the fundamentals like qubits, quantum gates, and quantum circuits. These are the building blocks for quantum algorithms, which hopefully can be utilized for optimization, for example, the QAOA (quantum approximate optimization algorithm), the VQE (variational quantum Eigensolver), and quantum annealing. They all build to optimize the problems in some way differently: QAOA through parameterized quantum circuits, VQE through approximations of ground states of the Hamiltonians, and quantum annealing through quantum evolution to low-energy solutions. We then form a loop between these quantum algorithms and regular machine learning tasks. Optimization impacts virtually all ML phases, from training neural networks, where one reduces loss functions; feature selection, where one aims to discover the most relevant subset of input variables; and hyperparameter optimization, which often involves expensive search procedures over extremely large combinatorial spaces. Quantum optimization techniques can therefore, in principle, accelerate such procedures through computational complexity reduction and enhancing solutions over challenging landscapes. Realistic simulations and case studies emphasize the degree to which hybrid quantum-classical algorithms have been employed in solving ML problems, that is, QSVMs, quantum-enhanced clustering, and quantum reinforcement learning. Despite their experimental nature, these applications already show encouraging results in terms of improved performance metrics as well as reduction in time-to-solution compared to classical-only solutions. Notwithstanding that, this new field is not bereft of real challenges. Quantum hardware suffers from hard limits on qubit fidelity, decoherence, and scalability in the current times. Furthermore, quantum circuit integration into broad ML pipelines requires novel architectures and software platforms. As a counter to those issues, this chapter surveys recent advances in quantum programming languages, simulators, and hybrid platforms like PennyLane, Qiskit, and TensorFlow Quantum. We conclude by looking to the future possibility that quantum optimization will revolutionize the machine learning landscape. As hardware improves and algorithmic complexity increases, the possibility of quantum-powered learning systems solving hard problems becomes increasingly accessible. From speeding up deep network training to enabling new types of unsupervised learning, quantum optimization holds the potential to recast computational tractability in machine learning. This chapter is an all-encompassing introduction and state-of-the-art work for students, researchers, and practitioners interested in using quantum optimization for practical ML applications. It sets the foundation for understanding how to pursue hybrid approaches (how they may be applied today in the real world and bracing oneself for disruption in the future).
We present quantum algorithms to efficiently perform discriminant analysis for dimensionality reduction and classification over an exponentially large input data set. Compared with the best-known classical algorithms, the quantum algorithms show an exponential speedup in both the number of training vectors M and the feature space dimension N . We generalize the previous quantum algorithm for solving systems of linear equations (2009 Phys. Rev. Lett. 103 150502 ) to efficiently implement a Hermitian chain product of k trace-normalized N × N Hermitian positive-semidefinite matrices with time complexity of . Using this result, we perform linear as well as nonlinear Fisher discriminant analysis for dimensionality reduction over M vectors, each in an N -dimensional feature space, in time , where denotes the tolerance error, and p is the number of principal projection directions desired. We also present a quantum discriminant analysis algorithm for data classification with time complexity .