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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Learning to Learn Variational quantum algorithm

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2023年第11期34卷 8430-8440页

作者： Huang, Rui Tan, Xiaoqing Xu, Qingshan Jinan Univ Coll Informat Sci & Technol Guangzhou 510632 Peoples R China Jinan Univ Coll Cyber Secur Guangzhou 510632 Peoples R China Adv Cryptog & Syst Secur Key Lab Sichuan Prov Chengdu 610025 Peoples R China

Variational quantum algorithms (VQAs) use classical computers as the quantum outer loop optimizer and update the circuit parameters to obtain an approximate ground state. In this article, we present a meta-learning variational quantum algorithm (meta-VQA) by recurrent unit, which uses a technique called "meta-learner." Motivated by the hybrid quantum-classical algorithms, we train classical recurrent units to assist quantum computing, learning to find approximate optima in the parameter landscape. Here, aiming to reduce the sampling number more efficiently, we use the quantum stochastic gradient descent method and introduce the adaptive learning rate. Finally, we deploy on the TensorFlow quantum processor within approximate quantum optimization for the Ising model and variational quantum eigensolver for molecular hydrogen (H-2), lithium hydride (LiH), and helium hydride cation (HeH+). Our algorithm can be expanded to larger system sizes and problem instances, which have higher performance on near-term processors.

关键词： Meta-learning quantum algorithm quantum computing quantum information quantum machine learning (QML)

来源：评论

学校读者我要写书评

暂无评论

quantum Circuit Ansatz: Patterns of Abstraction and Reuse of quantum algorithm Design 3

Quantum Circuit Ansatz: Patterns of Abstraction and Reuse of...

引用

3rd IEEE International Conference on quantum Software (IEEE QSW)

作者： Guo, Xiaoyu Muta, Takahiro Zhao, Jianjun Kyushu Univ Fukuoka Japan

ISBN: (纸本)9798350368482;9798350368475

quantum computing holds the potential to revolutionize various fields by efficiently tackling complex problems. At its core are quantum circuits, sequences of quantum gates manipulating quantum states. The selection of the right quantum circuit ansatz, which defines initial circuit structures and serves as the basis for optimization techniques, is crucial in quantum algorithm design. This paper presents a categorized catalog of quantum circuit ansatzes aimed at supporting quantum algorithm design and implementation. Each ansatz is described with details such as intent, motivation, applicability, circuit diagram, implementation, example, and see also. Practical examples are provided to illustrate their application in quantum algorithm design. The catalog aims to assist quantum algorithm designers by offering insights into the strengths and limitations of different ansatzes, thereby facilitating decision-making for specific tasks.

关键词： Ansatz quantum circuit design pattern quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for computing distances between subspaces

引用

PHYSICS LETTERS A 2024年 514卷

作者： Nghiem, Nhat A. SUNY Stony Brook Dept Phys & Astron Stony Brook NY 11794 USA

Geometry and topology have generated impacts far beyond their pure mathematical primitive, providing a solid foundation for many applicable tools. Typically, real -world data are represented as vectors, forming a linear subspace for a given data collection. Computing distances between different subspaces is generally a computationally challenging problem with both theoretical and applicable consequences, as, for example, the results can be used to classify data from different categories. Fueled by the fast-growing development of quantum algorithms, we consider such problems in the quantum context and provide a quantum algorithm for estimating two kinds of distance: Grassmann distance and ellipsoid distance. Under appropriate assumptions and conditions, the speedup of our quantum algorithm is exponential with respect to both the dimension of the given data and the number of data points. Some extensions regarding estimating different kinds of distance are then discussed as a corollary of our main quantum algorithmic method.

关键词： quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for Classical Multidimensional Scaling

引用

INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS 2024年第7期63卷 162-162页

作者： Liu, Xingao Zhou, Ri-Gui Guo, Wenyu You, Xiaorong Luo, Jia Suqian Univ Sch Informat Engn Suqian 223800 Jiangsu Peoples R China Shanghai Maritime Univ Coll Informat Engn Shanghai 201306 Peoples R China Shanghai Maritime Univ Res Ctr Intelligent Informat Proc & Quantum Intell Shanghai 201306 Peoples R China Changzhou Vocat Inst Text & Garment Coll Mech Engn Jiangsu 213164 Peoples R China Shangrao Normal Univ Sch Math & Computat Sci Jiangxi 334001 Peoples R China

Classical multidimensional scaling is an important dimensionality reduction method that is characterized by preserving the Euclidean distance between samples in high dimensional space in low dimensional space. However the high time complexity limits its application in massive samples and high-dimensional data scenarios. As a promising solution, a quantum algorithm for classical multidimensional scaling is proposed in this work, achieving polynomial speedup in terms of sample size compared to classical algorithms. Our algorithm is built on two quantum subroutines, one involving inner product and matrix multiplication, and the other utilizing quantum singular value estimation.

关键词： Classical multidimensional scaling Dimensionality reduction quantum algorithm quantum singular value estimation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for Anomaly Detection of Sequences

引用

ADVANCED quantum TECHNOLOGIES 2023年第8期6卷

作者： Guo, Ming-Chao Liu, Hai-Ling Pan, Shi-Jie Li, Wen-Min Gao, Fei Huang, Xin-Yi Qin, Su-Juan Wen, Qiao-Yan Beijing Univ Posts & Telecommun State Key Lab Networking & Switching Technol Beijing 100876 Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China Hong Kong Univ Sci & Technol Artificial Intelligence Thrust Informat Hub Guangzhou 511455 Peoples R China

Anomaly detection of sequences is a hot topic in data mining. Anomaly detection using piecewise aggregate approximation in the amplitude domain (called ADPAAD) is one of the widely used methods in anomaly detection of sequences. The core step in the classical algorithm for performing ADPAAD is to construct an approximate representation of the subsequence, where the elements of each subsequence are divided into several subsections according to the amplitude domain, and then the average of the subsections is computed. It is computationally expensive when processing large-scale sequences. In this paper, a quantum algorithm for ADPAAD is proposed, which can divide the subsequence elements and compute the average in parallel. The quantum algorithm can achieve polynomial speedups on the number of subsequences and the length of subsequences over its classical counterpart.

关键词： anomaly detection data mining polynomial speedup quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：