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

quantum algorithm for Boolean Equation Solving and quantum Algebraic Attack on Cryptosystems

Journal of Systems Science & Complexity 2022年第1期35卷 373-412页

作者： CHEN Yu-Ao GAO Xiao-Shan Academy of Mathematics and Systems Science Chinese Academy of SciencesBeijing 100190China University of Chinese Academy of Sciences Beijing 100049China

This paper presents a quantum algorithm to decide whether a Boolean equation system F has a solution and to compute one if F does have solutions with any given success *** runtime complexity of the algorithm is polynomial in the size of F and the condition number of certain Macaulay matrix associated with *** a consequence,the authors give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are polynomial in the size of *** authors apply the proposed quantum algorithm to the cryptanalysis of several important cryptosystems:The stream cipher Trivum,the block cipher AES,the hash function SHA-3/Keccak,the multivariate public key cryptosystems,and show that they are secure under quantum algebraic attack only if the corresponding condition numbers are *** leads to a new criterion for designing such cryptosystems which are safe against the attack of quantum computers:The corresponding condition number.

关键词： Block cipher AES Boolean equation solving condition number hash function SHA3/Keccak HHL algorithm MPKC polynomial system solving quantum algorithm stream cipher Trivum

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for soft margin support vector machine with hinge loss function

引用

The Journal of China Universities of Posts and Telecommunications 2022年第4期29卷 32-41页

作者： Liu Hailing Zhang Jie Qin Sujuan Gao Fei State Key Laboratory of Networking and Switching Technology Beijing University of Posts and TelecommunicationsBeijing 100876China State Key Laboratory of Cryptology P.O.Box 5159Beijing 100878China

Soft margin support vector machine(SVM)with hinge loss function is an important classification algorithm,which has been widely used in image recognition,text classification and so ***,solving soft margin SVM with hinge loss function generally entails the sub-gradient projection algorithm,which is very time-consuming when processing big training data *** achieve it,an efficient quantum algorithm is ***,this algorithm implements the key task of the sub-gradient projection algorithm to obtain the classical sub-gradients in each iteration,which is mainly based on quantum amplitude estimation and amplification algorithm and the controlled rotation *** with its classical counterpart,this algorithm has a quadratic speedup on the number of training data *** is worth emphasizing that the optimal model parameters obtained by this algorithm are in the classical form rather than in the quantum state *** enables the algorithm to classify new data at little cost when the optimal model parameters are determined.

关键词： soft margin support vector machine hinge loss function the sub-gradient projection algorithm quantum algorithm quadratic speedup

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Optimal deterministic quantum algorithm for the promised element distinctness problem ☆

引用

THEORETICAL COMPUTER SCIENCE 2024年 999卷

作者： Li, Guanzhong Li, Lvzhou Sun Yat Sen Univ Inst Quantum Comp & Software Sch Comp Sci & Engn Guangzhou 510006 Peoples R China Quantum Sci Ctr Guangdong Hong Kong Macao Greater Shenzhen 518045 Peoples R China

The element distinctness problem is to determine whether a string of N elements, i.e. x = ( x 1 , ... , x N ) where x;is an element of {1 , ... , M } and M >= N , contains two elements of the same value (a.k.a colliding pair), for which Ambainis proposed an optimal quantum algorithm. The idea behind Ambainis' algorithm is to first reduce the problem to the promised version in which x is promised to contain at most one colliding pair, and then design an algorithm A requiring O ( N 2 / 3 ) queries based on quantum walk search for the promise problem. However, A is probabilistic and may fail to give the right answer. We thus, in this work, design a deterministic quantum algorithm for the promise problem which never errs and requires O ( N 2 / 3 ) queries. This algorithm is proved optimal. Technically, we modify the quantum walk search operator on quasi -Johnson graph to have arbitrary phases, and then use Jordan's lemma as the analyzing tool to reduce the quantum walk search operator to the generalized Grover's operator. This allows us to utilize the recently proposed fixed -axis -rotation (FXR) method for deterministic quantum search, and hence achieve 100% success.

关键词： quantum computing quantum algorithm Element distinctness problem

来源：评论

学校读者我要写书评

暂无评论

Efficient and fail-safe quantum algorithm for the transport equation

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2024年 502卷

作者： Schalkers, Merel A. Moller, Matthias Delft Univ Technol Dept Appl Math Delft Netherlands

In this paper we present a scalable algorithm for fault-tolerant quantum computers for solving the transport equation in two and three spatial dimensions for variable grid sizes and discrete velocities, where the object walls are aligned with the Cartesian grid, the relative difference of velocities in each dimension is bounded by 1 and the total simulated time is dependent on the discrete velocities chosen. We provide detailed descriptions and complexity analyses of all steps of our quantum transport method (QTM) and present numerical results for 2D flows generated in Qiskit as a proof of concept. Our QTM is based on a novel streaming approach which leads to a reduction in the amount of CNOT gates required in comparison to state-of-the-art quantum streaming methods. As a second highlight of this paper we present a novel object encoding method, that reduces the complexity of the amount of CNOT gates required to encode walls, which now becomes independent of the size of the wall. Finally we present a novel quantum encoding of the particles' discrete velocities that enables a linear speed-up in the costs of reflecting the velocity of a particle, which now becomes independent of the amount of velocities encoded. Our main contribution consists of a detailed description of a fail-safe implementation of a quantum algorithm for the reflection step of the transport equation that can be readily implemented on a physical quantum computer. This fail-safe implementation allows for a variety of initial conditions and particle velocities and leads to physically correct particle flow behavior around the walls, edges and corners of obstacles. Combining these results we present a novel and fail-safe quantum algorithm for the transport equation that can be used for a multitude of flow configurations and leads to physically correct behavior. ( ) We finally show that our approach only requires O ��2 ��+ �� 2CNOT gates, which is �� max

关键词： quantum computing quantum computational fluid dynamics Transport equation quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

Synthetic Aperture Radar Imaging Using Computer Simulation of quantum algorithm and Circuits

引用

IEEE GEOSCIENCE AND REMOTE SENSING LETTERS 2025年 22卷

作者： Liu, Xiaowen Peng, Bo Luo, Ying Chen, Yichang Li, Haipeng Zhang, Qun Natl Univ Def Technol Test Ctr Xian 710100 Peoples R China Air Force Engn Univ Inst Informat & Nav Xian 710077 Peoples R China Collaborat Innovat Ctr Informat Sensing & Understa Xian 710077 Peoples R China Air Force Early Warning Acad Wuhan 430019 Peoples R China

In accord with imaging mechanism, by tackling the integrated quantum circuit without multiple preparations and measurements, a quantum algorithm with remarkable speedup for synthetic aperture radar (SAR) imaging is proposed to decrease the data storage and time consuming in this letter. First, the quantum algorithms for 2-D matched filtering and range cell migration correction (RCMC) are presented. Then, the relevant quantum circuits are designed and bonded together as an integrated quantum circuit for SAR imaging. It would be further applied to wide-swath imaging and sparse-driven radar imaging to form the corresponding quantum algorithm from quantum data to quantum data. The polynomial speedup in computational complexity is analyzed theoretically, and the needed quantum data are reduced exponentially compared to classical data. Experimental results obtained by computer simulation of quantum algorithm demonstrate that the proposed method can obtain the high-resolution SAR image and decrease at least 10(2) orders in complexity.

关键词： Radar imaging Radar polarimetry quantum algorithm Imaging quantum circuit Vectors Approximation algorithms Registers Qubit quantum state quantum circuit radar imaging synthetic aperture radar (SAR)

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm Framework for Discrete Probability Distributions With Applications to Renyi Entropy Estimation

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第5期70卷 3399-3426页

作者： Wang, Xinzhao Zhang, Shengyu Li, Tongyang Peking Univ Ctr Frontiers Comp Studies Beijing 100871 Peoples R China Peking Univ Sch Comp Sci Beijing 100871 Peoples R China Tencent Quantum Lab Shenzhen 518057 Peoples R China

Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating R & eacute;nyi entropies as specific examples. In particular, given a quantum oracle that prepares an n-dimensional quantum state & sum;(n )(i=1)root pi|(i)> , for alpha > 1 and 0 < alpha < 1 , our algorithm framework estimates alpha -R & eacute;nyi entropy H-alpha(p) to within additive error & varepsilon;with probability at least 2/3 using O(n(1-1/2 alpha)/ & varepsilon;+ root n-/& varepsilon;(1+1/2 alpha)) and O(n(1/2 alpha)/& varepsilon;(1+1/2 alpha)) queries, respectively. This improves the best known dependence in & varepsilon;as well as the joint dependence between n and 1/& varepsilon;. Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications.-

关键词： Entropy quantum algorithm Complexity theory Probability distribution Estimation Additives Amplitude estimation Entropy estimation R & eacute nyi entropy quantum algorithms quantum query complexity

来源：评论

学校读者我要写书评

暂无评论

A quantum algorithm for System Specifications Verification

引用

IEEE INTERNET OF THINGS JOURNAL 2024年第14期11卷 24775-24794页

作者： Zidan, Mohammed Eisa, Ahmed M. Qasymeh, Montasir Shoman, Mahmoud A. Ismail South Valley Univ Fac Comp & Artificial Intelligence Dept Artificial Intelligence Hurghada 1950003 Egypt Egyptian E Learning Univ Fac Comp & Informat Technol Giza 12611 Egypt Abu Dhabi Univ Elect & Comp Engn Dept Abu Dhabi U Arab Emirates Cairo Univ Fac Comp & Informat Cairo 12613 Egypt

Verifying system specifications is a crucial requirement in science and technology, as it improves accuracy and efficiency in systems engineering. However, traditional computers are time-consuming and cannot efficiently check the consistency of system specifications for classical and quantum systems due to exponential complexity costs. Currently, there is no quantum approach available for verifying consistency in quantum systems. This article introduces a novel quantum algorithm that utilizes the virtual degree of entanglement to efficiently check the consistency of unknown system specifications represented by m oracles. The proposed algorithm has a time complexity of O(m epsilon(-2)), which is independent of the input size n and depends only on a predetermined error margin epsilon, providing exponential speedup compared to the classical approach with a time complexity of O(m2(n)). Moreover, the proposed algorithm can handle weighted superposition input states, which are impossible for classical computers to handle. Thus, the algorithm has the potential to check the consistency of both quantum and classical system specifications. The proposed algorithm is realized experimentally using IBM's Aer simulator with an input size of n = 12. The experimental results closely aligned with the theoretical predictions, demonstrating the algorithm's efficiency in checking the consistency of system specifications. Specifically, the proposed algorithm achieved a quantum supremacy ratio of 300% to 3100% compared to the classical algorithm, highlighting its significant advantage in terms of time complexity. Additionally, the simulation results confirmed the efficiency of the proposed algorithm in checking the consistency of the quantum system's specifications.

关键词： quantum computing quantum entanglement Computers Qubit quantum algorithm quantum system Prediction algorithms Concurrence entanglement quantum algorithms quantum computing sensors systems engineering

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for Finding Impossible Differentials and Zero-Correlation Linear Hulls of Symmetric Ciphers 28th

Quantum Algorithm for Finding Impossible Differentials and Z...

引用

28th Australasian Conference on Information Security and Privacy (ACISP)

作者： Chen, Huiqin Li, Yongqiang Abla, Parhat Li, Zhiran Jiao, Lin Wang, Mingsheng Chinese Acad Sci Inst Informat Engn Beijing Peoples R China South China Normal Univ Sch Software Guangzhou Peoples R China State Key Lab Cryptol Beijing Peoples R China Univ Chinese Acad Sci Sch Cyber Secur Beijing Peoples R China

ISBN: (纸本)9783031354854;9783031354861

In this paper, we present quantum algorithms for finding impossible differentials and zero-correlation linear hulls, which are distinguishers for the two powerful attacks against symmetric ciphers of impossible differential attack and zero-correlation linear attack. Compared to classical methods, the proposed quantum algorithms possess many advantages. Firstly, our quantum algorithm for finding impossible differentials obtains the input and output differences by solving linear equation systems instead of searching in a limited space;Secondly, our quantum algorithm for zero-correlation linear hulls can investigate the key schedule's effect;Thirdly, the only computation cost of our algorithms is solving linear equation systems, and the size of the systems is not increasing as the round number increases. The core idea of our method is to use the Berstein-Vazirani algorithm to find 1-linear structures of Boolean functions. We check the validity of the proposed quantum algorithm with the SIMON block cipher family and RC5 block cipher. We show that the proposed algorithms can discover some 11-round, 12-round, 13-round, 16-round, and 19-round impossible differentials and zero-correlation linear hulls of SIMON cipher when considering the key schedules and 2.5-round impossible differential of RC5 when considering the round subkeys.

关键词： quantum algorithm Berstein-Vazirani algorithm Linear structure Impossible differential Zero-correlation linear hull

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：