In this article, we propose a general principle of quantum interference for quantum system, and based on this we propose a new type of computing machine, the duality computer, that may outperform in principle both cla...In this article, we propose a general principle of quantum interference for quantum system, and based on this we propose a new type of computing machine, the duality computer, that may outperform in principle both classical computer and the quantum computer. According to the general principle of quantum interference, the very essence of quantum interference is the interference of the sub-waves of the quantum system itself A quantum system considered here can be any quantum system： a single microscopic particle, a composite quantum system such as an atom or a molecule, or a loose collection of a few quantum objects such as two independent photons. In the duality computer, the wave of the duality computer is split into several sub-waves and they pass through different routes, where different computing gate operations are performed. These sub-waves are then re-combined to interfere to give the computational results. The quantum computer, however, has only used the particle nature of quantum object. In a duality computer, it may be possible to find a marked item from an unsorted database using only a single query, and all NP-complete problems may have polynomial algorithms. Two proof-of-the-principle designs of the duality computer are presented： the giant molecule scheme and the nonlinear quantum optics scheme. We also propose thought experiment to check the related fundamental issues, the measurement efficiency of a partial wave function.展开更多
The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to pract...The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on anEREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches. Keywords knapsack problem - NP-complete - parallel algorithm - optimal algorithm - memory conflict Supported by the National Natural Science Foundation of China under Grant No.60273075, the National High Technology Development 863 Program of China under Grant No.863-306-ZD-11-01-06.Ken-Li Li received his B.S. and M.S. degrees in mathematics from National University of Defense Technology and Central South University in 1995 and 2000 respectively and he is now a Ph.D. candidate in computer software and theory at Huazhong University of Science and Technology. His main research interests include parallel computing and combinatorial optimization.Ren-Fa Li received his Ph.D. degree in computer software and theory at Huazhong University of Science and Technology, and he is concurrently a professor and Ph.D. supervisor in School of Computer and Communication, Human University. His main research interests include network computing.Qing-Hua Li received his M.S. degree in computer science from Huazhong University of Science and Technology in 1981, and he is concurrently a professor and Ph.D. supervisor in School of Computer Science and Technology, Huazhong University of Science and Technology. His current research interests include parallel processing, combinatorial optimization, and grid computing.展开更多
Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed sy...Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed systems. In general, multi-constrained path selection with or without optimization is a NP-complete problem that can not be exactly solved in polynomial time. Hence, accurate constraints-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms. This paper aims to give a thorough, concise and fair evaluation of the most important multiple constraint-based QoS multicast routing algorithms known today, and it provides a descriptive overview and simulation results of these multi-constrained routing algorithms.展开更多
GMPLS(generalized multi protocol label switching)网络中的多约束QoS路由问题是要在诸如带宽、代价和延迟的约束条件下找到一条优化的路径.这个问题通常被认为是一个NP-完全问题.在研究共享风险链路组具有的启发信息的基础上,提出了...GMPLS(generalized multi protocol label switching)网络中的多约束QoS路由问题是要在诸如带宽、代价和延迟的约束条件下找到一条优化的路径.这个问题通常被认为是一个NP-完全问题.在研究共享风险链路组具有的启发信息的基础上,提出了一种具有共享风险链路启发信息的多约束预计算算法.该算法包含预计算和搜索两个部分.预计算主要是能创建和更新每个节点上的路由表.而后,搜索部分则可以在层次化的结构中选择满足约束条件的优化的路径.大量仿真数据表明,相应的方法能够取得满意的结果,可以有效地解决GMPLS网络中多约束的QoS路由问题.展开更多
基金The project supported by the National Fundamental Research Program under Grant No. 001CB309308, National Natural Science Foundation of China under Grant Nos. 10325521 and 60433050, and the SRFDP Program of the Ministry of Education of China
文摘In this article, we propose a general principle of quantum interference for quantum system, and based on this we propose a new type of computing machine, the duality computer, that may outperform in principle both classical computer and the quantum computer. According to the general principle of quantum interference, the very essence of quantum interference is the interference of the sub-waves of the quantum system itself A quantum system considered here can be any quantum system： a single microscopic particle, a composite quantum system such as an atom or a molecule, or a loose collection of a few quantum objects such as two independent photons. In the duality computer, the wave of the duality computer is split into several sub-waves and they pass through different routes, where different computing gate operations are performed. These sub-waves are then re-combined to interfere to give the computational results. The quantum computer, however, has only used the particle nature of quantum object. In a duality computer, it may be possible to find a marked item from an unsorted database using only a single query, and all NP-complete problems may have polynomial algorithms. Two proof-of-the-principle designs of the duality computer are presented： the giant molecule scheme and the nonlinear quantum optics scheme. We also propose thought experiment to check the related fundamental issues, the measurement efficiency of a partial wave function.
文摘The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on anEREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches. Keywords knapsack problem - NP-complete - parallel algorithm - optimal algorithm - memory conflict Supported by the National Natural Science Foundation of China under Grant No.60273075, the National High Technology Development 863 Program of China under Grant No.863-306-ZD-11-01-06.Ken-Li Li received his B.S. and M.S. degrees in mathematics from National University of Defense Technology and Central South University in 1995 and 2000 respectively and he is now a Ph.D. candidate in computer software and theory at Huazhong University of Science and Technology. His main research interests include parallel computing and combinatorial optimization.Ren-Fa Li received his Ph.D. degree in computer software and theory at Huazhong University of Science and Technology, and he is concurrently a professor and Ph.D. supervisor in School of Computer and Communication, Human University. His main research interests include network computing.Qing-Hua Li received his M.S. degree in computer science from Huazhong University of Science and Technology in 1981, and he is concurrently a professor and Ph.D. supervisor in School of Computer Science and Technology, Huazhong University of Science and Technology. His current research interests include parallel processing, combinatorial optimization, and grid computing.
文摘Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed systems. In general, multi-constrained path selection with or without optimization is a NP-complete problem that can not be exactly solved in polynomial time. Hence, accurate constraints-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms. This paper aims to give a thorough, concise and fair evaluation of the most important multiple constraint-based QoS multicast routing algorithms known today, and it provides a descriptive overview and simulation results of these multi-constrained routing algorithms.
文摘GMPLS(generalized multi protocol label switching)网络中的多约束QoS路由问题是要在诸如带宽、代价和延迟的约束条件下找到一条优化的路径.这个问题通常被认为是一个NP-完全问题.在研究共享风险链路组具有的启发信息的基础上,提出了一种具有共享风险链路启发信息的多约束预计算算法.该算法包含预计算和搜索两个部分.预计算主要是能创建和更新每个节点上的路由表.而后,搜索部分则可以在层次化的结构中选择满足约束条件的优化的路径.大量仿真数据表明,相应的方法能够取得满意的结果,可以有效地解决GMPLS网络中多约束的QoS路由问题.
