اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدQuantum Algorithms for Matching and Network Flows
37
0
0.0
(
0
)
تأليف
Andris Ambainis
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrt{m+n} log n), finding a maximal non-bipartite matching in time O(n^2 (sqrt{m/n} + log n) log n), and finding a maximal flow in an integer network in time O(min(n^{7/6} sqrt m * U^{1/3}, sqrt{n U} m) log n), where n is the number of vertices, m is the number of edges, and U <= n^{1/4} is an upper bound on the capacity of an edge.
قيم البحث
اقرأ أيضاً
As we begin to reach the limits of classical computing, quantum computing has emerged as a technology that has captured the imagination of the scientific world. While for many years, the ability to execute quantum algorithms was only a theoretical po
ssibility, recent advances in hardware mean that quantum computing devices now exist that can carry out quantum computation on a limited scale. Thus it is now a real possibility, and of central importance at this time, to assess the potential impact of quantum computers on real problems of interest. One of the earliest and most compelling applications for quantum computers is Feynmans idea of simulating quantum systems with many degrees of freedom. Such systems are found across chemistry, physics, and materials science. The particular way in which quantum computing extends classical computing means that one cannot expect arbitrary simulations to be sped up by a quantum computer, thus one must carefully identify areas where quantum advantage may be achieved. In this review, we briefly describe central problems in chemistry and materials science, in areas of electronic structure, quantum statistical mechanics, and quantum dynamics, that are of potential interest for solution on a quantum computer. We then take a detailed snapshot of current progress in quantum algorithms for ground-state, dynamics, and thermal state simulation, and analyze their strengths and weaknesses for future developments.
Suppose that three kinds of quantum systems are given in some unknown states $ket f^{otimes N}$, $ket{g_1}^{otimes K}$, and $ket{g_2}^{otimes K}$, and we want to decide which textit{template} state $ket{g_1}$ or $ket{g_2}$, each representing the feat
ure of the pattern class ${cal C}_1$ or ${cal C}_2$, respectively, is closest to the input textit{feature} state $ket f$. This is an extension of the pattern matching problem into the quantum domain. Assuming that these states are known a priori to belong to a certain parametric family of pure qubit systems, we derive two kinds of matching strategies. The first is a semiclassical strategy which is obtained by the natural extension of conventional matching strategies and consists of a two-stage procedure: identification (estimation) of the unknown template states to design the classifier (textit{learning} process to train the classifier) and classification of the input system into the appropriate pattern class based on the estimated results. The other is a fully quantum strategy without any intermediate measurement which we might call as the {it universal quantum matching machine}. We present the Bayes optimal solutions for both strategies in the case of K=1, showing that there certainly exists a fully quantum matching procedure which is strictly superior to the straightforward semiclassical extension of the conventional matching strategy based on the learning process.
Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical com
puters. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation, and in particular, on problems with an algebraic flavor.
In this work, we present a quantum neighborhood preserving embedding and a quantum local discriminant embedding for dimensionality reduction and classification. We demonstrate that these two algorithms have an exponential speedup over their respectiv
ely classical counterparts. Along the way, we propose a variational quantum generalized eigenvalue solver that finds the generalized eigenvalues and eigenstates of a matrix pencil $(mathcal{G},mathcal{S})$. As a proof-of-principle, we implement our algorithm to solve $2^5times2^5$ generalized eigenvalue problems. Finally, our results offer two optional outputs with quantum or classical form, which can be directly applied in another quantum or classical machine learning process.
While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function
over an $n$-dimensional convex body using $tilde{O}(n)$ queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires $tilde{Omega}(sqrt n)$ evaluation queries and $Omega(sqrt{n})$ membership queries.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
