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

quantum algorithms AND CIRCUITS FOR SCIENTIFIC COMPUTING

quantum INFORMATION & COMPUTATION 2016年第3-4期16卷 197-236页

作者： Bhaskar, Mihir K. Hadfield, Stuart Papageorgiou, Anargyros Petras, Iasonas Columbia Univ Dept Phys New York NY 10027 USA Columbia Univ Dept Comp Sci New York NY 10027 USA Princeton Univ Dept Comp Sci Princeton NJ 08540 USA

quantum algorithms for scientific computing require modules implementing fundamental functions, such as the square root, the logarithm, and others. We require algorithms that have a well-controlled numerical error, that are uniformly scalable and reversible (unitary), and that can be implemented efficiently. We present quantum algorithms and circuits for computing the square root, the natural logarithm, and arbitrary fractional powers. We provide performance guarantees in terms of their worst-case accuracy and cost. We further illustrate their performance by providing tests comparing them to the respective floating point implementations found in widely used numerical software.

关键词： quantum algorithms reversible circuits scientific computing

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for intersection and proximity problems

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2003年第5期E86A卷 1113-1119页

作者： Sadakane, K Sugawara, N Tokuyama, T Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808577 Japan

We discuss applications of quantum computation to geometric data processing. Especially, we give efficient algorithms for intersection problems and proximity problems. Our algorithms are based on Brassard et al.'s amplitude amplification method, and analogous to Buhrman et al.'s algorithm for element distinctness. Revealing these applications is useful for classifying geometric problems, and also emphasizing potential usefulness of quantum computation in geometric data processing. Thus, the results will promote research and development of quantum computers and algorithms.

关键词： quantum algorithms computational geometry intersection proximity amplitude amplification

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for typical hard problems: a perspective of cryptanalysis

引用

quantum INFORMATION PROCESSING 2020年第6期19卷 1-26页

作者： Suo, Jingwen Wang, Licheng Yang, Sijia Zheng, Wenjie Zhang, Jiankang Beijing Univ Posts & Telecommun State Key Lab Networking & Switching Technol Beijing 100876 Peoples R China Univ Southampton Elect & Comp Sci Southampton SO17 1BJ Hants England

In typical well-known cryptosystem, the hardness of classical problems plays a fundamental role in ensuring its security. While, with the booming of quantum computation, some classical hard problems tend to be vulnerable when confronted with the already-known quantum attacks, as a result, it is necessary to develop the post-quantum cryptosystem to resist the quantum attacks. With the purpose to bridge the two disciplines, it is significant to summarize known quantum algorithms and their threats toward these cryptographic intractable problems from a perspective of cryptanalysis. In this paper, we discussed the designing methodology, algorithm framework and latest progress of the mathematic hard problems on which the typical cryptosystems depend, including integer factorization problem, discrete logarithmic problem and its variants, lattice problem, dihedral hidden subgroup problems and extrapolated dihedral coset problem. It illustrated the reason why some cryptosystems such as RSA and ECC are not resistant to quantum attacks, yet some of them like lattice cryptosystems remain intact facing quantum attacks.

关键词： quantum algorithms Cryptanalysis Lattice problem Dihedral hidden subgroup problem

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms on Walsh transform and Hamming distance for Boolean functions

引用

quantum INFORMATION PROCESSING 2018年第6期17卷 1-17页

作者： Xie, Zhengwei Qiu, Daowen Cai, Guangya Sun Yat Sen Univ Inst Comp Sci Theory Sch Data & Comp Sci Guangzhou 510006 Guangdong Peoples R China Sun Yat Sen Univ Guangdong Key Lab Informat Secur Technol Guangzhou 510006 Guangdong Peoples R China Jiangsu Univ Technol Sch Math & Phys Changzhou 213001 Peoples R China Inst Super Tecn Inst Telecomunicacoes Dept Matemat Ave Rovisco Pais P-1049001 Lisbon Portugal

Walsh spectrum or Walsh transform is an alternative description of Boolean functions. In this paper, we explore quantum algorithms to approximate the absolute value of Walsh transform W-f at a single point z(0) (i.e., |W-f (z(0))|) for n-variable Boolean functions with probability at least 8/pi(2) using the number of O(1/vertical bar W-f (z(0))vertical bar epsilon) queries, promised that the accuracy is epsilon, while the best known classical algorithm requires O(2(n)) queries. The Hamming distance between Boolean functions is used to study the linearity testing and other important problems. We take advantage of Walsh transform to calculate the Hamming distance between two n-variable Boolean functions f and g using O(1) queries in some cases. Then, we exploit another quantum algorithm which converts computing Hamming distance between two Boolean functions to quantum amplitude estimation (i.e., approximate counting). If Ham(f, g) = t not equal 0, we can approximately compute Ham(f,g) with probability at least 2/3 by combining our algorithm and Approx - Count (f, epsilon) algorithm using the expected number of Theta(root N/([epsilon t] + 1) + root t(N-t)/[epsilon t] + 1) queries, promised that the accuracy is epsilon. Moreover, our algorithm is optimal, while the exact query complexity for the above problem epsilon is Theta(N) and the query complexity with the accuracy epsilon is O(1/epsilon(2) N/(t + 1)) in classical algorithm, where N = 2(n). Finally, we present three exact quantum query algorithms for two promise problems on Hamming distance using O(1) queries, while any classical deterministic algorithm solving the problem uses O(2(n)) queries.

关键词： Walsh transform Hamming distance Bernstein-Vazirani algorithm quantum algorithms quantum amplitude estimation

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms FOR GIBBS SAMPLING AND HITTING-TIME ESTIMATION

引用

quantum INFORMATION & COMPUTATION 2017年第1-2期17卷 41-64页

作者： Chowdhury, Anirban Narayan Somma, Rolando D. Univ New Mexico Ctr Quantum Informat & Control Albuquerque NM 87131 USA New Mexico Consortium Los Alamos Res Pk Los Alamos NM 87544 USA Los Alamos Natl Lab Theoret Div Los Alamos NM 87545 USA

We present quantum algorithms for solving two problems regarding stochastic processes. The first algorithm prepares the thermal Gibbs state of a quantum system and runs in time almost linear in,root N beta/Z and polynomial in log(l/c), where N is the Hilbert space dimension, beta is the inverse temperature, Z is the partition function, and c is the desired precision of the output state. Our quantum algorithm exponentially improves the complexity dependence on 1/c and polynomially improves the dependence on beta of known quantum algorithms for this problem. The second algorithm estimates the hitting time of a Markov chain. For a sparse stochastic matrix P, it runs in time almost linear in 1/(c Delta(3/2)), where c is the absolute precision in the estimation and Delta is a parameter determined by P, and whose inverse is an upper bound of the hitting time. Our quantum algorithm quadratically improves the complexity dependence on 1/c and 1/Delta of the analog classical algorithm for hitting-time estimation. Both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.

关键词： quantum algorithms stochastic processes

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for Matching Problems

引用

THEORY OF COMPUTING SYSTEMS 2009年第3期45卷 613-628页

作者： Doern, Sebastian Univ Ulm Inst Theoret Informat D-89069 Ulm Germany

We present quantum algorithms for the following matching problems in unweighted and weighted graphs with n vertices and m edges: Finding a maximal matching in general graphs in time O(root nm log(2)n). Finding a maximum matching in general graphs in time O(n root m log(2)n). Finding a maximum weight matching in bipartite graphs in time O(n root m N log(2)n), where N is the largest edge weight. 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 Spalek (Proceedings of STACS'06, pp. 172-183, 2006).

关键词： quantum algorithms Graph theory Matching problems

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for structured prediction

引用

quantum MACHINE INTELLIGENCE 2022年第2期4卷 1-25页

作者： Sepehry, Behrooz Iranmanesh, Ehsan Friedlander, Michael P. Ronagh, Pooya 1QB Informat Technol 1QBit Vancouver BC Canada Univ British Columbia Vancouver BC Canada Inst Quantum Comp Waterloo ON Canada Univ Waterloo Waterloo ON Canada

We introduce two quantum algorithms for solving structured prediction problems. We first show that a stochastic gradient descent that uses the quantum minimum finding algorithm and takes its probabilistic failure into account solves the structured prediction problem with a runtime that scales with the square root of the size of the label space, and in similar to O (1/..) with respect to the precision,.., of the solution. Motivated by robust inference techniques in machine learning, we then introduce another quantum algorithm that solves a smooth approximation of the structured prediction problem with a similar quantum speedup in the size of the label space and a similar scaling in the precision parameter. In doing so, we analyze a variant of stochastic gradient descent for convex optimization in the presence of an additive error in the calculation of the gradients, and show that its convergence rate does not deteriorate if the additive errors are of the order O(v root epsilon). This algorithm uses quantum Gibbs sampling at temperature O(epsilon) as a subroutine. Based on these theoretical observations, we propose a method for using quantum Gibbs samplers to combine feedforward neural networks with probabilistic graphical models for quantum machine learning. Our numerical results using Monte Carlo simulations on an image tagging task demonstrate the benefit of the approach.

关键词： quantum algorithms Statistical learning Structured prediction Support vector machines Computational complexity Query complexity quantum minimum finding quantum Gibbs sampling Stochastic gradient descent Stochastic subgradient methods Stochastic average gradient methods Smooth approximation

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms in Electromagnetic Propagation Modelling for Telecommunications

引用

IEEE ACCESS 2023年 11卷 111545-111565页

作者： Novak, Roman Jozef Stefan Inst Dept Commun Syst Ljubljana 1000 Slovenia

Modelling of electromagnetic wave propagation in telecommunications has evolved from empirical models to highly deterministic ray tracing and numerical methods. The extraordinary computational effort of these methods and their wave nature seem ideally suited to be approached by quantum algorithms. We first examine current progress by reviewing recent proposals in the field. We scrutinize potentially advantageous quantum architectures, ranging from mainstream gate-level computers and near-term, mid-scale noisy architectures with limited capabilities, to adiabatic and annealing approaches that are already in commercial use. We analyze the weaknesses and strengths of recent proposals. Beyond the core algorithm, mechanisms to bridge the quantum and classical worlds are of particular interest. Extremely diverse algorithm specifications, from those based on Hamiltonian simulations and emulation of variational optimization to the unconstrained binary formulation, are compared with the use of pure gate-level circuits and known quantum subroutines. We show that the graph Laplacian, given its ability to integrate boundary conditions, is uniquely suited for quantum propagation modelling algorithms rooted in differential numerical methods. quantum computers could overcome the temporal and spatial limitations of classical methods for larger computational domains and, to some extent, address the problems of dispersion and stability in finite-difference approximations. The ability to express the solution of a problem as an eigenvalue problem turns out to be an advantage in the quantum world, where eigenvalues and eigenvectors are inextricably intertwined with quantum mechanics. In this paper, we identify the most promising techniques and scenarios that hold the greatest potential.

关键词： Electromagnetics numerical modelling radio wave propagation ray tracing simulation telecommunications quantum algorithms wireless communications

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for finding constant-sized sub-hypergraphs

引用

THEORETICAL COMPUTER SCIENCE 2016年 609卷 569-582页

作者： Le Gall, Francois Nishimura, Harumichi Tani, Seiichiro Univ Tokyo Grad Sch Informat Sci & Technol Bunkyo Ku Tokyo 1138656 Japan Nagoya Univ Grad Sch Informat Sci Chikusa Ku Nagoya Aichi 4648601 Japan NTT Corp NTT Commun Sci Labs 3-1 Morinosato Wakamiya Atsugi Kanagawa 2430198 Japan

We develop a general framework to construct quantum algorithms that detect if a 3-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a pre-specified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez (2013) [12], and extends the methodology designed by Lee, Magniez and Santha (2013) [18] for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a 4-clique in a 3-uniform hypergraph on n vertices with query complexity O(n(1.883)), and a quantum algorithm for determining if a ternary operator over a set of size n is associative with query complexity O(n(2.113)). (C) 2015 Elsevier B.V. All rights reserved.

关键词： quantum algorithms Hypergraphs quantum walk

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms Applied to Satellite Mission Planning for Earth Observation

引用

IEEE JOURNAL OF SELECTED TOPICS IN APPLIED EARTH OBSERVATIONS AND REMOTE SENSING 2023年 16卷 7062-7075页

作者： Rainjonneau, Serge Tokarev, Igor Iudin, Sergei Rayaprolu, Saaketh Pinto, Karan Lemtiuzhnikova, Daria Koblan, Miras Barashov, Egor Kordzanganeh, Mo Pflitsch, Markus Melnikov, Alexey Thales Alenia Space F-31100 Toulouse France Terra Quantum AG CH-9000 St Gallen Switzerland

Earth imaging satellites are a crucial part of our everyday lives that enable global tracking of industrial activities. Use cases span many applications, from weather forecasting to digital maps, carbon footprint tracking, and vegetation monitoring. However, there are limitations;satellites are difficult to manufacture, expensive to maintain, and tricky to launch into orbit. Therefore, satellites must be employed efficiently. This poses a challenge known as the satellite mission planning problem, which could be computationally prohibitive to solve on large scales. However, close-to-optimal algorithms, such as greedy reinforcement learning and optimization algorithms can often provide satisfactory resolutions. This article introduces a set of quantum algorithms to solve the mission planning problem and demonstrate an advantage over the classical algorithms implemented thus far. The problem is formulated as maximizing the number of high-priority tasks completed on real datasets containing thousands of tasks and multiple satellites. This work demonstrates that through solution-chaining and clustering, optimization and machine learning algorithms offer the greatest potential for optimal solutions. This article notably illustrates that a hybridized quantum-enhanced reinforcement learning agent can achieve a completion percentage of 98.5% over high-priority tasks, significantly improving over the baseline greedy methods with a completion rate of 75.8%. The results presented in this work pave the way to quantum-enabled solutions in the space industry and, more generally, future mission planning problems across industries.

关键词： Earth observation quantum algorithms quantum optimization quantum reinforcement learning satellite mission planning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：