检索结果-内蒙古大学图书馆

作者： Zhang, Kaining University of Sydney

学位级别：硕士

Non-convex optimization is an essential problem in the field of machine learning. Optimization methods for non-convex problems can be roughly di- vided into first-order methods and second-order methods, depending on the or- der of the derivative to the objective function they used. Generally, to find the local minima, the second-order methods are applied to find the effective direc- tion to escape the saddle point. Specifically, finding the Negative Curvature is considered as the subroutine to analyze the characteristic of the saddle point. However, the calculation of the Negative Curvature is expensive, which prevents the practical usage of second-order algorithms. In this thesis, we present an efficient quantum algorithm aiming to find the negative curvature direction for escaping the saddle point, which is a critical subroutine for many second-order non-convex optimization algorithms. We prove that our algorithm could produce the target state corresponding to the negative curvature direction with query complexity ˜ O(polylog(d)ϵ −1 ), where d is the dimension of the optimization function. The quantum negative curva- ture finding algorithm is exponentially faster than any known classical method, which takes time at least O(dϵ −1/2 ). Moreover, we propose an efficient quan- tum algorithm to achieve the classical read-out of the target state. Our classical read-out algorithm runs exponentially faster on the degree of d than existing counterparts.

关键词： quantum algorithm optimization state readout

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm for Finding a Hamilton Circuit

引用

Communications in Theoretical Physics 2001年第4期35卷 385-388页

作者： GUOHao LONGGui－Lu 等 DepartmentofPhysics TsinghuaUniversityBeijing100084China DepartmentofPhysics TsinghuaUniversityBeijing100084China；InstituteofTheoreticalPhysicsTheChineseAcademyofSciencesBeijing

A quantum algorithm for solving the classical NP-complete problem - the Hamilton circuit is presented. The algorithm employs the quantum SAT and the quantum search algorithms. The algorithm is square-root faster than classical algorithm, and becomes exponentially faster than classical algorithm if nonlinear quantum mechanical computer is used.

关键词： quantum algorithm Hamilton circuit NP-problem

来源：评论

学校读者我要写书评

暂无评论

An Exact quantum algorithm for a Restricted Subtraction Game

引用

INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS 2020年第5期59卷 1504-1511页

作者： Huang, Yunqi Ye, Zekun Zheng, Shenggen Li, Lvzhou Sun Yat Sen Univ Inst Comp Sci Theory Sch Data & Comp Sci Guangzhou 510006 Peoples R China Peng Cheng Lab Ctr Quantum Comp Shenzhen 518055 Peoples R China Sun Yat Sen Univ Minist Educ Key Lab Machine Intelligence & Adv Comp Guangzhou 510006 Peoples R China

An algorithm is exact if it always produces the correct answer on any input. Coming up with exact quantum algorithms that substantially outperform the best classical algorithm has been a quite challenging task. Nim game is a well-known combinatorial game which has a complete mathematical theory, and many kinds of Nim games have been studied in the literature. One famous kind of Nim games are subtraction games played with one heap of tokens, with players taking turns removing from the heap a number of tokens belonging to a specified subtraction set. The last player to move wins. In this paper, we propose a restricted subtraction game with the subtraction set determined by a specified matrix, and present an exact quantum algorithm to solve it. We show that the query complexity of our quantum algorithm is O(n(3/2)), while the classical exact query complexity is Theta(n(2)).

关键词： Query complexity Subtraction game quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

A novel quantum algorithm for ant colony optimisation

IET QUANTUM COMMUNICATION

引用

IET quantum COMMUNICATION 2022年第1期3卷 13-29页

作者： Ghosh, Mrityunjay Dey, Nivedita Mitra, Debdeep Chakrabarti, Amlan HCL Technol Noida Uttar Pradesh India Univ Calcutta Kolkata India QRDLab North Dumdum W Bengal India

Ant colony optimisation (ACO) is a commonly used meta-heuristic to solve complex combinatorial optimisation problems like the travelling salesman problem (TSP), vehicle routing problem (VRP) etc. However, classical ACO algorithms provide better optimal solutions but do not reduce computation time overhead to a significant extent. algorithmic speed-up can be achieved by using parallelism offered by quantum computing. Existing quantum algorithms to solve ACO are either quantum-inspired classical algorithms or hybrid quantum-classical algorithms. Since all these algorithms need the intervention of classical computing, leveraging the true potential of quantum computing on real quantum hardware remains a challenge. This study's main contribution is to propose a fully quantum algorithm to solve ACO, enhancing the quantum information processing toolbox in the fault-tolerant quantum computing (FTQC) era. We have solved the single source single destination (SSSD) shortest-path problem using our proposed adaptive quantum circuit for representing the dynamic pheromone-updating strategy in real IBMQ devices. Our quantum ACO technique can be further used as a quantum ORACLE to solve complex optimisation problems in a fully quantum setup with significant speed up upon the availability of more qubits.

关键词： ant colony optimisation QACO quantum algorithm quantum ant quantum circuit synthesis quantum computing

来源：评论

学校读者我要写书评

暂无评论

Efficient quantum algorithm for dissipative nonlinear differential equations

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2021年第35期118卷 2026805118-2026805118页

作者： Liu, Jin-Peng Kolden, Herman Oie Krovi, Hari K. Loureiro, Nuno F. Trivisa, Konstantina Childs, Andrew M. Univ Maryland Joint Ctr Quantum Informat & Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Univ Maryland Dept Math College Pk MD 20742 USA Norwegian Univ Sci & Technol Dept Phys NO-7491 Trondheim Norway MIT Plasma Sci & Fus Ctr 77 Massachusetts Ave Cambridge MA 02139 USA Raytheon BBN Technol Quantum Engn & Comp Cambridge MA 02138 USA Univ Maryland Inst Phys Sci & Technol College Pk MD 20742 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA

Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic n-dimensional ordinary differential equations. Assuming R < 1, where R is a parameter characterizing the ratio of the non-linearity and forcing to the linear dissipation, this algorithm has complexity T-2 q poly(log T, log n, log 1/epsilon)/epsilon, where T is the evolution time, E is the allowed error, and q measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for R >= root 2 Finally, we discuss potential applications, showing that the R < 1 condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of R.

关键词： quantum algorithm nonlinear differential equations Carleman linearization Navier-Stokes equation plasma dynamics

来源：评论

学校读者我要写书评

暂无评论

New quantum algorithm for studying NP-complete problems

引用

REPORTS ON MATHEMATICAL PHYSICS 2003年第1期52卷 25-33页

作者： Ohya, M Volovich, IV Tokyo Univ Sci Dept Informat Sci Noda Chiba 2788510 Japan VA Steklov Math Inst Moscow 117966 Russia

Ordinary approach to quantum algorithm is based on quantum Turing machine or quantum circuits. It is known that this approach is not powerful enough to solve NP-complete problems. In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm.

关键词： quantum algorithm NP-complete problem chaotic dynamics

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm based on the ε-random linear disequations for the continuous hidden shift problem

引用

quantum INFORMATION PROCESSING 2021年第10期20卷 347-347页

作者： Bae, Eunok Lee, Soojoon Kyung Hee Univ Dept Math Seoul 02447 South Korea Kyung Hee Univ Res Inst Basic Sci Seoul 02447 South Korea

There have been several research works on the hidden shift problem, quantum algorithms for the problem, and their applications. However, all the results have focused on discrete groups with discrete oracle functions. In this paper, we define the continuous hidden shift problem on R-n with a continuous oracle function as an extension of the hidden shift problem, and also define the epsilon-random linear disequations which is a generalization of the random linear disequations. By employing the newly defined concepts, we show that there exists a quantum computational algorithm which solves this problem in time polynomial in n.

关键词： quantum algorithm Continuous hidden shift problem epsilon-Random linear disequations

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm and experimental demonstration for the subset sum problem

引用

Science China(Information Sciences) 2022年第8期65卷 261-274页

作者： Qilin ZHENG Pingyu ZHU Shichuan XUE Yang WANG Chao WU Xinyao YU Miaomiao YU Yingwen LIU Mingtang DENG Junjie WU Ping XU Institute for Quantum Information and State Key Laboratory of High Performance Computing College of Computer Science and TechnologyNational University of Defense Technology

To solve the subset sum problem, a well-known nondeterministic polynomial-time complete problem that is widely used in encryption and resource scheduling, we propose a feasible quantum algorithm that utilizes fewer qubits to encode and achieves quadratic speedup. Specifically, this algorithm combines an amplitude amplification algorithm with quantum phase estimation, and requires n + t + 1 qubits and O(2(0.5+o(1))n) operations to obtain the solution, where n is the number of elements, and t is the number of qubits used to store the eigenvalues. To verify the performance of the algorithm, we simulate the algorithm with the online quantum simulator of IBM named ibmq simulator using Qiskit and then run it on two IBM quantum computers called ibmq santiago and ibmq bogota. The experimental results indicate that compared with the brute force algorithm, the proposed algorithm results in quadratic acceleration for the problem of a set S with four elements and two subsets whose sum equals target w. Using the iterator twice, we obtain success probabilities of 0.940 ± 0.004, 0.751 ± 0.040, and 0.665 ± 0.060 on the simulator, ibmq santiago, and ibmq bogota, respectively, and the fidelity between the theoretical and experimental quantum states is calculated to be 0.944 ± 0.002, 0.753 ± 0.017, and 0.657 ± 0.028, respectively. If the error rates of the experimental quantum logic gates can be reduced, the success probabilities of the proposed algorithm on real quantum devices can be further improved.

关键词： quantum algorithm subset sum quadratic speedup encryption algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

Research of quantum algorithm for Adaptive Active Noise Control System

Research of Quantum Algorithm for Adaptive Active Noise Cont...

引用

International Conference on Advanced Materials and Engineering Materials (ICAMEM 2011)

作者： Jiang Wei Shenyang Ligong Univ Liaoning Peoples R China

ISBN: (纸本)9783037853559

Adaptive active noise control based on least mean square (LMS) algorithm is a linear adaptive filter so that it cannot obtain desired noise reduction. quantum algorithm is combined with noise control to form quantum adaptive controller. quantum adaptive algorithm is discussed completely and noise control system is simulated in order to analyze the effects of noise control.

关键词： adaptive active noise control noise reduction quantum algorithm adaptive controller

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm FOR SIMULATING REAL TIME EVOLUTION OF LATTICE HAMILTONIANS

引用

SIAM JOURNAL ON COMPUTING 2023年第6期52卷 250-284页

作者： Haah, Jeongwan Hastings, Matthew B. Kothari, Robin Low, Guang Hao Microsoft Quantum & Microsoft Res Redmond WA 98052 USA

We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on n qubits for time T up to error epsilon using O (nT polylog(nT/epsilon)) gates with depth O (T polylog(nT/epsilon)). Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in nT and polylogarithmic in 1/epsilon. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires (sic) (nT) gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To the best of our knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb--Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb--Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.

关键词： quantum algorithm local Hamiltonian simulation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：