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

quantum algorithm for Dynamic Programming Approach for DAGs and Applications

LOBACHEVSKII JOURNAL OF MATHEMATICS 2023年第2期44卷 699-712页

作者： Khadiev, K. Safina, L. Russian Acad Sci Zavoisky Phys Tech Inst Kazan Sci Ctr Fed Res Ctr Kazan 420029 Russia Kazan Fed Univ Inst Computat Math & Informat Technol Kazan 420008 Tatarstan Russia

In this paper, we present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is O(root(n) over capm log (n) over cap), and the running time of the best known deterministic algorithm is O(n + m), where n is the number of vertices, (n) over cap is the number of vertices with at least one outgoing edge;m is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non-constant depth evaluation. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.

关键词： quantum computation quantum models quantum algorithm query model graph dynamic programming DAG Boolean formula Zhegalkin polynomial DNF AND-OR-NOT formula NAND computational complexity classical vs. quantum Boolean formula evaluation

来源：评论

学校读者我要写书评

暂无评论

Demonstration of essentiality of entanglement in a Deutsch-like quantum algorithm

引用

Science China(Physics,Mechanics & Astronomy) 2018年第6期61卷 1-7页

作者： He-Liang Huang Ashutosh K. Goswami Wan-Su Bao Prasanta K. Panigrahi Chinese Academy Sciences Centre for Excellence and Synergetic Innovation Centre in Quantum Information and Quantum Physics University of Science and Technology of China Hefei 230026 China Hefei National Laboratory for Physical Sciences at Microscale Department of modern Physics University of Science and Technology of China Hefei 230026 China Indian Institute of Science Education and Research Kolkata Mohanpur 741 246 India

quantum algorithms can be used to efficiently solve certain classically intractable problems by exploiting quantum ***, the effectiveness of quantum entanglement in quantum computing remains a question of debate. This study presents a new quantum algorithm that shows entanglement could provide advantages over both classical algorithms and quantum algorithms without entanglement. Experiments are implemented to demonstrate the proposed algorithm using superconducting *** show the viability of the algorithm and suggest that entanglement is essential in obtaining quantum speedup for certain problems in quantum computing. The study provides reliable and clear guidance for developing useful quantum algorithms.

关键词： quantum computing quantum entanglement quantum algorithm Deutsch＇s problem

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm for Toeplitz matrix-vector multiplication

引用

Chinese Physics B 2023年第10期32卷 248-253页

作者：高尚杨宇光 Faculty of Information Technology Beijing University of TechnologyBeijing 100124China

Toeplitz matrix-vector multiplication is widely used in various fields,including optimal control,systolic finite field multipliers,multidimensional convolution,*** this paper,we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O(κpolylogn),whereκand 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix,*** the case with an unknown generating function,we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L_(1)-normρof the displacement of the structured *** to the good use of the special properties of Toeplitz matrices,the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.

关键词： quantum algorithm Toeplitz matrix-vector multiplication circulant matrix

来源：评论

学校读者我要写书评

暂无评论

Experimental Implementation of quantum algorithm for Association Rules Mining

引用

IEEE JOURNAL ON EMERGING AND SELECTED TOPICS IN CIRCUITS AND SYSTEMS 2022年第3期12卷 676-684页

作者： Yu, Chao-Hua Jiangxi Univ Finance & Econ Sch Informat Management Nanchang 330032 Jiangxi Peoples R China

Recently, a quantum algorithm for a fundamentally important task in data mining, association rules mining (ARM), called qARM for short, has been proposed. Notably, qARM achieves significant speedup over its classical counterpart for implementing the main task of ARM, i.e., finding frequent itemsets from a transaction database. In this paper, we experimentally implement qARM on both real quantum computers and a quantum computing simulator via the IBM quantum computing platform. In the first place, we design quantum circuits of qARM for a 2 x 2 transaction database (i.e., a transaction database involving two transactions and two items), and run it on four real five-qubit IBM quantum computers as well as on the simulator. For a larger 4 x 4 transaction database which would lead to circuits with more qubits and a higher depth than the currently accessible IBM real quantum devices can handle, we also construct the quantum circuits of qARM and execute them on "aer_simulator" alone. Both experimental results show that all the frequent itemsets from the two transaction databases are successfully derived as desired, demonstrating the correctness and feasibility of qARM. Our work may serve as a benchmarking, and provide prototypes for implementing qARM for larger transaction databases on both noisy intermediate-scale quantum devices and universal fault-tolerant quantum computers.

关键词： quantum algorithm association rules mining IBM quantum computer IBM quantum simulator

来源：评论

学校读者我要写书评

暂无评论

Lattice quantum algorithm for the Schrodinger wave equation in 2+1 dimensions with a demonstration by modeling soliton instabilities

引用

quantum INFORMATION PROCESSING 2005年第6期4卷 457-469页

作者： Yepez, Jeffrey Vahala, George Vahala, Linda USAF Res Lab Bedford MA 01731 USA Coll William & Mary Dept Phys Williamsburg VA 23187 USA Old Dominion Univ Coll Engn & Technol Norfolk VA 23529 USA

A lattice-based quantum algorithm is presented to model the non-linear Schrodinger-like equations in 2 + 1 dimensions. In this lattice-based model, using only 2 qubits per node, a sequence of unitary collide (qubit-qubit interaction) and stream (qubit translation) operators locally evolve a discrete field of probability amplitudes that in the long-wavelength limit accurately approximates a non-relativistic scalar wave function. The collision operator locally entangles pairs of qubits followed by a streaming operator that spreads the entanglement throughout the two dimensional lattice. The quantum algorithmic scheme employs a non-linear potential that is proportional to the moduli square of the wave function. The model is tested on the transverse modulation instability of a one dimensional soliton wave train, both in its linear and non-linear stages. In the integrable cases where analytical solutions are available, the numerical predictions are in excellent agreement with the theory.

关键词： non-linear Schrodinger wave equation quantum algorithm soliton dynamics non-linear quantum mechanical instability quantum computing computational physics

来源：评论

学校读者我要写书评

暂无评论

An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables

引用

quantum INFORMATION PROCESSING 2020年第7期19卷 213-213页

作者： Chen, Chien-Yuan Natl Univ Kaohsiung Dept Comp Sci & Informat Engn 700 Kaohsiung Univ Rd Kaohsiung Taiwan

In this paper, we propose a novel quantum learning algorithm, based on Younes' quantum circuit, to find dependent variables of the Boolean function f: {0,1}(n)->{0,1} with one uncomplemented product of two variables. Typically, in the worst-case scenario, two dependent variables are found by evaluating the function O (n) times. However, our proposed quantum algorithm only requires O (log(2)n) function operations in the worst-case. Additionally, we evaluate the average number to perform the function. In the average case, our algorithm requires O (1) function operations.

关键词： quantum algorithm quantum learning algorithm The Bernstein-Vazirani algorithm

来源：评论

学校读者我要写书评

暂无评论

A low failure rate quantum algorithm for searching maximum or minimum

引用

quantum INFORMATION PROCESSING 2020年第8期19卷 1-28页

作者： Chen, Yanhu Wei, Shijie Gao, Xiong Wang, Cen Tang, Yinan Wu, Jian Guo, Hongxiang Beijing Univ Posts & Telecommun Inst Informat Photon & Opt Commun Beijing 100876 Peoples R China Beijing Acad Quantum Informat Sci Beijing 100193 Peoples R China Tsinghua Univ State Key Lab Low Dimens Quantum Phys Beijing 100084 Peoples R China Tsinghua Univ Dept Phys Beijing 100084 Peoples R China

Although Durr and Hoyer have proposed state-of-the-art quantum algorithm (DHA) for searching minimum value, the lower limit of DHA's successful probability is 1/2. Also, DHA requires approximately (log(2) N)(2) copies of the initial state. In this paper, we propose a new quantum maximum or minimum searching algorithm (QUMMSA). In big data scenarios, according to sparse sampling with different densities, we can estimate the corresponding precision parameters. QUMMSA can improve the successful probability close to 100%. Furthermore, with the quantum exact search algorithm, QUMMSA only requires approximately log2 N copies of the initial state to solve this problem. Since preparing an arbitrary quantum state is a problem with exponential complexity, our algorithm has a greater advantage with the increasing database size. In addition, we first propose a general method for circuits construction, which can be used in any database. An experiment implemented in an IBM superconducting processor and a numerical simulation of a 6-qubit system to solve a real issue indicate the feasibility and efficiency of QUMMSA. QUMMSA can serve as a subroutine in various quantum algorithms which involves searching maximum or minimum.

关键词： quantum algorithm Searching minimum or maximum problem quantum circuits Superconducting experiments

来源：评论

学校读者我要写书评

暂无评论

Recovering the Original Simplicity: Succinct and Exact quantum algorithm for the Welded Tree Problem

引用

algorithmICA 2024年第12期86卷 3719-3758页

作者： Li, Guanzhong Li, Lvzhou Luo, Jingquan Sun Yat sen Univ Inst Quantum Comp & Software Sch Comp Sci & Engn Guangzhou 510006 Peoples R China

This work revisits quantum algorithms for the well-known welded tree problem, proposing a succinct quantum algorithm based on the simple coined quantum walks. It iterates the naturally defined coined quantum walk operator for a classically precomputed number of iterations, and measures. The number of iterations is linear in the depth of the tree. The success probability of this procedure is inversely linear in the depth of the tree. Moreover, it is the same for all instances of the problem of a fixed size, therefore, we can use the exact quantum amplitude amplification subroutine to answer with probability 1. This gives an exponential speedup over any classical algorithm for the same problem. The significance of the results may be seen as follows. (i) Our algorithm is rather simple compared with the one in (Jeffery and Zur, STOC'2023), which not only breaks the stereotype that coined quantum walks can only achieve quadratic speedups over classical algorithms, but also demonstrates the power of the simplest quantum walk model. (ii) Our algorithm achieves certainty of success for the first time. Thus, it becomes one of the few examples that exhibit exponential separation between exact quantum and randomized query complexities.

关键词： The welded tree problem quantum walk quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm for Evaluating the Hamming Distance

引用

Computers, Materials & Continua 2022年第4期71卷 1065-1078页

作者： Mohammed Zidan Manal G.Eldin Mahmoud Y.Shams Mohamed Tolan Ayman Abd-Elhamed Mahmoud Abdel-Aty Department of Artificial Intelligence Hurghada Faculty of Computers and Artificial IntelligenceSouth Valley UniversityEgypt Faculty of Engineering King Salman International UniversitySouth SinaiEgypt Department of Mathematics and Computer Science Faculty of ScienceBeni-Suef UniversityBeni-SuefEgypt Department of Machine Learning and Information Retrieval Faculty of Artificial IntelligenceKafrelsheikh UniversityEgypt Mechanical Department Faculty of Technology and EducationSuez UniversitySuezEgypt Faculty of Technological Industries King Salman International UniversitySouth SinaiEgypt Faculty of Engineering at Mataria Helwan UniversityCairoEgypt Department of Mathematics Faculty of SciencesSohag University82524 SohagEgypt

We present a novel quantum algorithm to evaluate the hamming distance between two unknown oracles via measuring the degree of entanglement between two ancillary *** particular,we use the power of the entanglement degree based quantum computing model that preserves at most the locality of interactions within the quantum model *** model uses one of two techniques to retrieve the solution of a quantum computing problem at *** the first technique,the solution of the problem is obtained based on whether there is an entanglement between the two ancillary qubits or *** the second,the solution of the quantum computing problem is obtained as a function in the concurrence value,and the number of states that can be generated from the Boolean *** proposed algorithm receives two oracles,each oracle represents an unknown Boolean function,then it measures the hamming distance between these two *** hamming distance is evaluated based on the second *** is shown that the proposed algorithm provides exponential speedup compared with the classical counterpart for Boolean functions that have large numbers of Boolean *** proposed algorithm is explained via a case ***,employing recently developed experimental techniques,the proposed algorithm has been verified using IBM’s quantum computer simulator.

关键词： quantum computing quantum algorithm quantum circuit

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm for approximating the influences of Boolean functions and its applications

引用

quantum INFORMATION PROCESSING 2015年第6期14卷 1787-1797页

作者： Li, Hongwei Yang, Li Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing 100093 Peoples R China Henan Inst Educ Sch Math & Stat Zhengzhou 450046 Henan Peoples R China Chinese Acad Sci Data Assurance & Commun Secur Res Ctr Beijing 100093 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China

We investigate the influences of variables on a Boolean function f based on the quantum Bernstein-Vazirani algorithm. A previous paper (Floess et al. in Math Struct Comput Sci 23:386, 2013) has proved that if an n-variable Boolean function f (x(1) ,..., x(n)) does not depend on an input variable x(i), using the Bernstein-Vazirani circuit for f will always output y that has a 0 in the ith position. We generalize this result and show that, after running this algorithm once, the probability of getting a 1 in each position i is equal to the dependence degree of f on the variable x(i), i.e., the influence of x(i) on f. Based on this, we give an approximation algorithm to evaluate the influence of any variable on a Boolean function. Next, as an application, we use it to study the Boolean functions with juntas and construct probabilistic quantum algorithms to learn certain Boolean functions. Compared with the deterministic algorithms given by Floess et al., our probabilistic algorithms are faster.

关键词： The Bernstein-Vazirani algorithm quantum algorithm Influence of Boolean function

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：