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

A quantum algorithm for solving weapon target assignment problem

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2023年第1期125卷

作者： Acar, Erdi Hatipoglu, Saim Yilmaz, Ihsan Istanbul Rumeli Univ Fac Engn & Nat Sci Dept Comp Engn Istanbul Turkiye Canakkale Onsekiz Mart Univ Sch Grad Studies Dept Comp Engn Canakkale Turkiye Canakkale Onsekiz Mart Univ Fac Engn Dept Comp Engn Canakkale Turkiye

quantum computers, known to have the potential for exponential speedup in solving some problems due to their superposition property, are expected to facilitate the solution of NP-hard optimisation problems. This study proposes a quantum algorithm to solve the weapon target assignment problem (WTAP), one of the NP-hard optimisation problems. The proposed quantum algorithm is a gate-based approach, and scenario examples are executed on Qiskit quantum computing platform and IBM Lima quantum computer with Falcon r4T processor type. The results manifest that the proposed quantum algorithm has low space and time complexity, demonstrating its memory and computational resources efficiency.

关键词： quantum algorithm quantum computing Weapon target assignment NP-hard problem

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm for finding collision-inducing disturbance vectors in SHA-1

引用

PHYSICA SCRIPTA 2023年第11期98卷 115106-115106页

作者： Duan, Jiheng Li, Minghui Ian, Hou Univ Macau Fac Sci & Technol Dept Phys & Chem Taipa Macau Sar Peoples R China Univ Macau Inst Appl Phys & Mat Engn Taipa Macau Sar Peoples R China

Modern cryptographic protocols rely on sophisticated hash functions to generate quasi-unique numbers that serve as signatures for user authentication and other security verifications. The security could be compromised by finding texts hash-mappable to identical numbers, forming so-called collision attack. Seeding a disturbance vector in the hash mapping to obtain a successful collision is that a major focus of cryptography study in the past two decades to improve hash protocols. We propose an algorithm that takes advantage of entangled quantum states for concurrent seeding of candidate disturbance vectors, out of which the one entailing collision is selected through a combination of quantum search, phase gating, diffusion gating, and information feedbacks from classical computing machinery. The complexity reduction is shown to be on the order of O(2(n/2+1)) where n is the number of qubits encoding addresses. We demonstrate the practicality of the proposed by an implementation scheme based on degenerate optical parametric oscillators.

关键词： SHA cryptography quantum algorithm quantum entanglement optical parametric oscillator

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm for Solving Eigenproblem of the Laplacian Matrix of a Fully Connected Weighted Graph

引用

ADVANCED quantum TECHNOLOGIES 2023年第7期6卷

作者： Liu, Hai-Ling Wan, Lin-Chun Yu, Chao-Hua Pan, Shi-Jie Qin, Su-Juan Gao, Fei 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 Jiangxi Univ Finance & Econ Sch Informat Management Nanchang 330032 Peoples R China

Solving eigenproblem of the Laplacian matrix of a fully connected weighted graph has wide applications in data science, machine learning, and image processing, etc. However, this is very challenging because it involves expensive matrix operations. Here, an efficient quantum algorithm is proposed to solve it. Specifically, the optimal Hamiltonian simulation technique based on the block-encoding framework is adopted to implement the quantum simulation of the Laplacian matrix. Then, the eigenvalues and eigenvectors of the Laplacian matrix are extracted by the quantum phase estimation algorithm. The core of this entire algorithm is to construct a block-encoding of the Laplacian matrix. To achieve this, how to construct block-encoding of operators containing the information of the weight matrix and the degree matrix, respectively are shown in detail, and the block-encoding of the Laplacian matrix is further obtained. Compared with its classical counterpart, this algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex. It is also shown that this algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.

关键词： block-encoding fully connected weighted graph Laplacian matrix quantum algorithm solving eigenproblem

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for solving the test-suite minimization problem

引用

COGENT ENGINEERING 2021年第1期8卷 Article: 1882116页

作者： Hussein, Hager Younes, Ahmed Abdelmoez, Walid Arab Acad Sci & Technol Coll Comp & Informat Technol Dept Software Engn Alexandria Egypt Alexandria Univ Fac Sci Dept Math & Comp Sci Alexandria Egypt Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England

Test-suite minimization problem is an essential problem in software engineering as its application helps to improve the software quality. This paper proposes a quantum algorithm to solve the test-suite minimization problem with high probability in O(root 2(n)), where n is the number of test cases. It generates an incomplete superposition to find the best solution. It also handles the non-uniform amplitudes' distribution case for the system with multisolutions. The proposed algorithm uses amplitude amplification techniques to search for the minimum number of test cases required to test all the requirements. The proposed algorithm employs two quantum search algorithms, Younes et al. algorithm for quantum searching via entanglement and partial diffusion to prepare incomplete superpositions that represent different search spaces such that the number of test cases is incremented in each search space, and updated Arima's algorithm to handle the multisolutions case. The updated Arima's algorithm searches for a quantum state that satisfies an oracle that represent the instance of the test-suite minimization problem.

关键词： quantum algorithm Test-Suite Minimization Superposition Preparation quantum Search

来源：评论

学校读者我要写书评

暂无评论

An improved quantum algorithm for data fitting

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2023年 613卷

作者： Lei, Jiancheng Song, Tingting Liu, Ling Zhang, Kejia Jinan Univ Coll Cyber Secur Guangzhou 510632 Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China Jinan Univ Coll Informat Sci & Technol Guangzhou 510632 Peoples R China Heilongjiang Univ Sch Math Sci Harbin 150080 Peoples R China

As researchers focus on the field of quantum machine learning, there are more and more quantum algorithms for data fitting. However, the majority of quantum algorithms for data fitting are only applicable to sparse matrices, which bring a large number of limitations to their application. In this paper, to solve this problem, we propose a quantum algorithm for data fitting for general matrices, not only sparse and dense matrices. The quantum algorithm is mainly composed of three subroutines which are generating target state, quantum state tomography and estimating fit quality. The time complexity of the quantum algorithm is O (kappa 4 parallel to A parallel to Fpolylog(MN)(M ' 2 log(M ')2/epsilon 3+ 1/(epsilon epsilon 2))), where A is an element of RMxN, kappa is the conditional number of matrix A dagger A is an element of RNxN, ||A||F is the Frobenius norm of A, M ' is the maxima number of fit functions in allowing fit, epsilon is the fitting error, and epsilon is the error of fit quality estimation. Moreover, our quantum algorithm is independent of the sparsity of the matrix, so our algorithm has wide application in dense matrices and poses a new state of the art for solving dense data fitting. (c) 2023 Elsevier B.V. All rights reserved.

关键词： quantum algorithm quantum machine learning Data fitting

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm for Boolean Functions Processing

引用

IEEE ACCESS 2024年 12卷 164503-164519页

作者： Aljuaydi, Fahad Abdelazim, Samar Darwish, Mohamed M. Zidan, Mohammed Prince Sattam bin Abdulaziz Univ Coll Sci & Humanities Dept Math Al Kharj 11942 Saudi Arabia Assiut Univ Fac Comp & Informat Dept Comp Sci Asyut 71515 Egypt Univ Tabuk Univ Coll Al Wajh Dept Comp Sci Tabuk 71491 Saudi Arabia Hurghada Univ Fac Comp & Artificial Intelligence Dept Artificial Intelligence Hurghada Egypt

Detecting junta variables is a critical issue in Boolean function analysis, circuit design optimization, and machine learning feature selection. In this paper, we investigate a novel quantum computation algorithm based on the Mz operator. The algorithm takes in an unknown oracle concealing a Boolean function with n variables and an unknown input state, which can be quantum or classical. The input state can be complete or incomplete quantum basis states, and it can be a weighted or uniform superposition of basis states. The proposed approach determines whether a given variable is a junta with a time cost of O (2 /& varepsilon;(2) ) and a memory cost of 2n+ 6. The algorithm is analyzed and experimentally implemented using the Qiskit simulator and IBM's real quantum computer. Experimental results show that the proposed approach achieved a quantum supremacy ratio 6300% higher than that of the classical method when verifying junta variables for Boolean functions with 12 variables. The results suggest that the proposed quantum method can verify junta variables in scenarios beyond the capabilities of current classical or quantum methods.

关键词： quantum computing Boolean functions Qubit Computational modeling quantum entanglement Machine learning Costs Testing Computer science Time complexity quantum algorithm junta problem Mz entanglement

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm for testing and learning resiliency of a Boolean function

引用

quantum INFORMATION PROCESSING 2019年第2期18卷 51-51页

作者： Li, Hongwei Henan Finance Univ Sch Math & Stat Zhengzhou 450046 Henan Peoples R China

A quantum algorithm to evaluate the resiliency of a Boolean function is explored. Recently, Chakraborty and Maitra (Cryptogr Commun 8(3):401-413, 2016) have provided quantum algorithms to check the non-resiliency of a Boolean function. However, the shortage of their algorithms is that they just output YES or NO. Refining one of the algorithms, a quantum algorithm is proposed here, which can describe the extent of the non-resiliency by E-almost resiliency under the condition NO.

关键词： Almost resilient function Resilient function quantum algorithm Walsh spectrum

来源：评论

学校读者我要写书评

暂无评论

quantum mean centering for block-encoding-based quantum algorithm

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2022年 607卷

作者： Liu, Hai-Ling Yu, Chao-Hua Wan, Lin-Chun Qin, Su-Juan Gao, Fei Wen, Qiaoyan 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 Jiangxi Univ Finance & Econ Sch Informat Management Nanchang 330032 Jiangxi Peoples R China Southwest Univ Sch Comp & Informat Sci Chongqing 400715 Peoples R China

Mean Centering (MC) is an important data preprocessing technique, which has a wide range of applications in data mining, machine learning, and multivariate statistical analysis. When the data set is large, this process will be time-consuming. In this paper, we propose an efficient quantum MC algorithm based on the block-encoding technique, which enables the existing quantum algorithms can get rid of the assumption that the original data set has been classically mean-centered. Specifically, we first adopt the strategy that MC can be achieved by multiplying by the centering matrix C, i.e., removing the row means, column means and row-column means of the original data matrix X can be expressed as XC, CX and CXC, respectively. This allows many classical problems involving MC, such as Principal Component Analysis (PCA), to directly solve the matrix algebra problems related to XC, CX or CXC. Next, we can employ the block-encoding technique to realize MC. To achieve it, we first show how to construct the block-encoding of the centering matrix C, and then further obtain the block-encodings of XC, CX and CXC. Finally, we describe one by one how to apply our MC algorithm to PCA and other algorithms. (c) 2022 Published by Elsevier B.V.

关键词： Mean centering quantum algorithm Block-encoding Matrix algebra problems The centering matrix

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm FOR SIMULATING NON-SPARSE HAMILTONIANS

引用

quantum INFORMATION & COMPUTATION 2020年第7-8期20卷 597-615页

作者： Wang, Chunhao Wossnig, Leonard Univ Waterloo Inst Quantum Comp Waterloo ON Canada Univ Waterloo Sch Comp Sci Waterloo ON Canada Univ Texas Austin Dept Comp Sci Austin TX 78712 USA UCL Dept Comp Sci London England

We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is O(t root N vertical bar vertical bar H vertical bar vertical bar polylog(N, vertical bar vertical bar H vertical bar vertical bar, 1/epsilon)), where t is the evolution time, N is the dimension of the system, and epsilon is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving (O) over tilde (root N) dependence for both applications.

关键词： Hamiltonian simulation quantum algorithm linear combination of unitaries quantum walk quantum machine learning qRAM linear systems solver

来源：评论

学校读者我要写书评

暂无评论

Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems

引用

NEW JOURNAL OF PHYSICS 2016年第7期18卷 1-1页

作者： Mandra, Salvatore Guerreschi, Gian Giacomo Aspuru-Guzik, Alan Harvard Univ Dept Chem & Chem Biol 12 Oxford St Cambridge MA 02138 USA

We present an exact quantum algorithm for solving the Exact Satisfiability problem, which belongs to the important NP-complete complexity class. The algorithm is based on an intuitive approach that can be divided into two parts: the first step consists in the identification and efficient characterization of a restricted subspace that contains all the valid assignments of the Exact Satisfiability;while the second part performs a quantum search in such restricted subspace. The quantum algorithm can be used either to find a valid assignment (or to certify that no solution exists) or to count the total number of valid assignments. The query complexities for the worst-case are respectively bounded by O(root 2(n-M')) and O(2(n-M')), where n is the number of variables and M' the number of linearly independent clauses. Remarkably, the proposed quantum algorithm results to be faster than any known exact classical algorithm to solve dense formulas of Exact Satisfiability. As a concrete application, we provide the worst-case complexity for the Hamiltonian cycle problem obtained after mapping it to a suitable Occupation problem. Specifically, we show that the time complexity for the proposed quantum algorithm is bounded by O(2(n/4)) for 3-regular undirected graphs, where n is the number of nodes. The same worst-case complexity holds for(3, 3)-regular bipartite graphs. As a reference, the current best classical algorithm has a (worst-case) running time bounded by O(2(31n/96)). Finally, when compared to heuristic techniques for Exact Satisfiability problems, the proposed quantum algorithm is faster than the classical WalkSAT and Adiabatic quantum Optimization for random instances with a density of constraints close to the satisfiability threshold, the regime in which instances are typically the hardest to solve. The proposed quantum algorithm can be straightforwardly extended to the generalized version of the Exact Satisfiability known as Occupation problem. The general version o

关键词： quantum algorithm exact satisfiability NP-complete problem computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：