共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
Progress in Quantum Algorithms 总被引:2,自引:0,他引:2
Peter W. Shor 《Quantum Information Processing》2004,3(1-5):5-13
We discuss the progress (or lack of it) that has been made in discovering algorithms for computation on a quantum computer. Some possible reasons are given for the paucity of quantum algorithms so far discovered, and a short survey is given of the state of the field.
PACS: 03.67.Lx 相似文献
3.
Model-based localization, the task of estimating an object's pose from sensed and corresponding model features, is a fundamental task in machine vision. Exact constant time localization algorithms have been developed for the case where the sensed features and the model features are the same type. Still, it is not uncommon for the sensed features and the model features to be of different types, i.e., sensed data points may correspond to model faces or edges. Previous localization approaches have handled different model and sensed features of different types via sampling and synthesizing virtual features to reduce the problem of matching features of dissimilar types to the problem of matching features of similar types. Unfortunately, these approaches may be suboptimal because they introduce artificial errors. Other localization approaches have reformulated object localization as a nonlinear least squares problem where the error is between the sensed data and model features in image coordinates (the Euclidean image error metric). Unfortunately, all of the previous approaches which minimized the Euclidean image error metric relied on gradient descent methods to find the global minima, and gradient descent methods may suffer from problems of local minima. In this paper, we describe an exact, efficient solution to the nonlinear least squares minimization problem based upon resultants, linear algebra, and numerical techniques. On a SPARC 20, our localization algorithm runs in a few microseconds for rectilinear polygonal models, a few milliseconds for generic polygonal models, and one second for generalized polygonal models (models composed of linear edges and circular arcs). 相似文献
4.
Preemptive scheduling problems on parallel machines are classic problems. Given the goal of minimizing the makespan, they are polynomially solvable even for the most general model of unrelated machines. In these problems, a set of jobs is to be assigned to run on a set of m machines. A job can be split into parts arbitrarily and these parts are to be assigned to time slots on the machines without parallelism, that is, for every job, at most one of its parts can be processed at each time. Motivated by sensitivity analysis and online algorithms, we investigate the problem of designing robust algorithms for constructing preemptive schedules. Robust algorithms receive one piece of input at a time. They may change a small portion of the solution as an additional part of the input is revealed. The capacity of change is based on the size of the new piece of input. For scheduling problems, the supremum ratio between the total size of the jobs (or parts of jobs) which may be re-scheduled upon the arrival of a new job j, and the size of j, is called migration factor. We design a strongly optimal algorithm with the migration factor $1-\frac{1}{m}$ for identical machines. Strongly optimal algorithms avoid idle time and create solutions where the (non-increasingly) sorted vector of completion times of the machines is lexicographically minimal. In the case of identical machines this results not only in makespan minimization, but the created solution is also optimal with respect to any ? p norm (for p>1). We show that an algorithm of a smaller migration factor cannot be optimal with respect to makespan or any other ? p norm, thus the result is best possible in this sense as well. We further show that neither uniformly related machines nor identical machines with restricted assignment admit an optimal algorithm with a constant migration factor. This lower bound holds both for makespan minimization and for any ? p norm. Finally, we analyze the case of two machines and show that in this case it is still possible to maintain an optimal schedule with a small migration factor in the cases of two uniformly related machines and two identical machines with restricted assignment. 相似文献
5.
Fast and Robust General Purpose Clustering Algorithms 总被引:3,自引:0,他引:3
General purpose and highly applicable clustering methods are usually required during the early stages of knowledge discovery exercises. k-MEANS has been adopted as the prototype of iterative model-based clustering because of its speed, simplicity and capability to work within the format of very large databases. However, k-MEANS has several disadvantages derived from its statistical simplicity. We propose an algorithm that remains very efficient, generally applicable, multidimensional but is more robust to noise and outliers. We achieve this by using medians rather than means as estimators for the centers of clusters. Comparison with k-MEANS, EXPECTATION and MAXIMIZATION sampling demonstrates the advantages of our algorithm. 相似文献
6.
Amit Hagar 《Minds and Machines》2007,17(2):233-247
I discuss the philosophical implications that the rising new science of quantum computing may have on the philosophy of computer
science. While quantum algorithms leave the notion of Turing-Computability intact, they may re-describe the abstract space
of computational complexity theory hence militate against the autonomous character of some of the concepts and categories
of computer science.
相似文献
Amit HagarEmail: |
7.
Sebastian Dörn 《Theory of Computing Systems》2009,45(3):613-628
We present quantum algorithms for the following matching problems in unweighted and weighted graphs with n vertices and m edges:
Our quantum algorithms are faster than the best known classical deterministic algorithms for the corresponding problems.
In particular, the second result solves an open question stated in a paper by Ambainis and Špalek (Proceedings of STACS’06,
pp. 172–183, 2006). 相似文献
• | Finding a maximal matching in general graphs in time . |
• | Finding a maximum matching in general graphs in time . |
• | Finding a maximum weight matching in bipartite graphs in time , where N is the largest edge weight. |
8.
In this article, we formulate and study quantum analogues of randomized search heuristics, which make use of Grover search (in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM, New York, 1996) to accelerate the search for improved offsprings. We then specialize the above formulation to two specific search heuristics: Random Local Search and the (1+1) Evolutionary Algorithm. We call the resulting quantum versions of these search heuristics Quantum Local Search and the (1+1) Quantum Evolutionary Algorithm. We conduct a rigorous runtime analysis of these quantum search heuristics in the computation model of quantum algorithms, which, besides classical computation steps, also permits those unique to quantum computing devices. To this end, we study the six elementary pseudo-Boolean optimization problems OneMax, LeadingOnes, Discrepancy, Needle, Jump, and TinyTrap. It turns out that the advantage of the respective quantum search heuristic over its classical counterpart varies with the problem structure and ranges from no speedup at all for the problem Discrepancy to exponential speedup for the problem TinyTrap. We show that these runtime behaviors are closely linked to the probabilities of performing successful mutations in the classical algorithms. 相似文献
9.
Robust Algorithms For Generalized Pham Systems 总被引:1,自引:0,他引:1
10.
Given a multivariate polynomial P(X
1,…,X
n
) over a finite field
, let N(P) denote the number of roots over
. The modular root counting problem is given a modulus r, to determine N
r
(P)=N(P)mod r. We study the complexity of computing N
r
(P), when the polynomial is given as a sum of monomials. We give an efficient algorithm to compute N
r
(P) when the modulus r is a power of the characteristic of the field. We show that for all other moduli, the problem of computing N
r
(P) is
-hard. We present some hardness results which imply that our algorithm is essentially optimal for prime fields. We show an
equivalence between maximum-likelihood decoding for Reed-Solomon codes and a root-finding problem for symmetric polynomials.
P. Gopalan’s and R.J Lipton’s research was supported by NSF grant CCR-3606B64.
V. Guruswami’s research was supported in part by NSF grant CCF-0343672 and a Sloan Research Fellowship. 相似文献
11.
混合量子进化算法及其应用 总被引:1,自引:0,他引:1
文章将量子进化算法(QEA)和粒子群算法(PSO)互相结合,提出了两种混合量子进化算法。第一种算法叫做嵌入式粒子群量子进化算法,其主要思想是将简化的PSO进化方程嵌入QEA的进化操作中,简化了QEA算法的结构,增强了QEA跳出局部极值的能力。第二种算法叫做量子二进制粒子群算法,其主要思想是将QEA中的量子染色体的概念引入二进制粒子群算法(BPSO),提高了BPSO算法保持种群多样性的能力和运算速度。通过对0-1背包问题和多用户检测问题的求解表明,新的算法不仅操作更简单,而且全局搜索能力有了显著的提高。 相似文献
12.
通过将Miller-Rabin素性检测的思想拓展到多项式域,随机二分搜索可应用到多项式分解中。并以此为基础,分别针对有限域和代数数域改进了两种概率性算法。第一种算法在有限域上每次分解模素数的多项式的失败概率最多为1/4;第二种算法在代数数域上每次分解模素理想P的多项式的失败概率最多为1/2,当代数数域为偶数次扩展或者P|( p)满足 p为素数且4|p-1的形式时,失败概率至多为3/8。和原有算法相比较降低了失败概率。这两种算法都在分解之前进行了素性判断,这一特性可用于生成不可归约多项式。在讨论代数数域情况时,给出了完整的多项式运算的时间复杂证明,弥补了代数数域内多项式计算理论模型上的空白。 相似文献
13.
《Journal of Symbolic Computation》2002,33(5):701-733
To approximate all roots (zeros) of a univariate polynomial, we develop two effective algorithms and combine them in a single recursive process. One algorithm computes a basic well isolated zero-free annulus on the complex plane, whereas another algorithm numerically splits the input polynomial of the n th degree into two factors balanced in the degrees and with the zero sets separated by the basic annulus. Recursive combination of the two algorithms leads to computation of the complete numerical factorization of a polynomial into the product of linear factors and further to the approximation of the roots. The new root-finder incorporates the earlier techniques of Schönhage, Neff/Reif, and Kirrinnis and our old and new techniques and yields nearly optimal (up to polylogarithmic factors) arithmetic and Boolean cost estimates for the computational complexity of both complete factorization and root-finding. The improvement over our previous record Boolean complexity estimates is by roughly the factor of n for complete factorization and also for the approximation of well-conditioned (well isolated) roots, whereas the same algorithm is also optimal (under both arithmetic and Boolean models of computing) for the worst case input polynomial, whose roots can be ill-conditioned, forming clusters. (The worst case complexity bounds for root-finding are supported by our previous algorithms as well.) All algorithms allow processor efficient acceleration to achieve solution in polylogarithmic parallel time. 相似文献
14.
基于特征子空间的稳健波束形成算法能够用于改善一般导向矢量失配的稳健性,而且相比于其它算法实现简单,然而方法在低的信噪比和较高的信号加噪声子空间维数条件下,性能急剧恶化,而且信号加噪声子空间的维数必须是已知的。为改善波束形成稳定性,提出了基于L-曲线的方法用于信号子空间及其维数的稳健估计,使得该算法的应用条件得以满足,其中还提出了广义SINR,并详细分析了理想条件下信号子空间的选取对算法性能的影响,最后进行了详细的仿真试验和性能分析,验证了所提出方法的正确性和有效性。 相似文献
15.
In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries
and quantum examples.
Pacs: 03.67.Lx, 89.80.+h, 02.70.-c 相似文献
Hunziker et al.[Quantum Information Processing, to appear] conjectured that for any class C of Boolean functions, the number of quantum black-box queries which are required to exactly identify an unknown function from C is , where is a combinatorial parameter of the class C. We essentially resolve this conjecture in the affirmative by giving a quantum algorithm that, for any class C, identifies any unknown function from C using quantum black-box queries. | |
We consider a range of natural problems intermediate between the exact learning problem (in which the learner must obtain all bits of information about the black-box function) and the usual problem of computing a predicate (in which the learner must obtain only one bit of information about the black-box function). We give positive and negative results on when the quantum and classical query complexities of these intermediate problems are polynomially related to each other. | |
Finally, we improve the known lower bounds on the number of quantum examples (as opposed to quantum black-box queries) required for ɛ, Δ-PAC learning any concept class of Vapnik-Chervonenkis dimension d over the domain from to . This new lower bound comes closer to matching known upper bounds for classical PAC learning. |
16.
17.
A. D. Zakrevskii 《Automation and Remote Control》2004,65(6):978-996
Weakly specified Boolean functions and systems are considered. A series of practically effective algorithms are proposed for their implementation by AND/EXOR circuits, which rely on the optimization of polynomial representations and the solutions of appropriate matrix logic equations. The obtained results are extended to multivalued logic. 相似文献
18.
van Dam 《Algorithmica》2008,34(4):413-428
Abstract. In this article we investigate how we can employ the structure of combinatorial objects like Hadamard matrices and weighing
matrices to devise new quantum algorithms. We show how the properties of a weighing matrix can be used to construct a problem
for which the quantum query complexity is significantly lower than the classical one. It is pointed out that this scheme captures
both Bernstein and Vazirani's inner-product protocol, as well as Grover's search algorithm.
In the second part of the article we consider Paley's construction of Hadamard matrices, which relies on the properties of
quadratic characters over finite fields. We design a query problem that uses the Legendre symbol χ (which indicates if an element of a finite field F
q
is a quadratic residue or not). It is shown how for a shifted Legendre function f
s
(i)=χ(i+s) , the unknown s ∈ F
q
can be obtained exactly with only two quantum calls to f
s
. This is in sharp contrast with the observation that any classical, probabilistic procedure requires more than log q + log ((1-ɛ )/2) queries to solve the same problem. 相似文献
19.