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

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

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for Solving the Wave Equation on a Hexagonal Grid

引用

IEEE ACCESS 2024年 12卷 131009-131022页

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

Numerical methods based on finite differences for solving the wave equation are prone to various errors, a challenge that also applies to the semi-discrete case of a recently proposed quantum algorithm that preserves continuous time while discretizing space into a quantum state vector. The inherent limitations of quantum processing, which affect the generality and extensibility of the quantum algorithm compared to classical numerical solvers, are offset by the logarithmic scaling of the number of qubits with the number of grid points. The higher grid density in combination with the higher-order approximation of the continuous Laplacian operator improves the numerical accuracy. In contrast to the Dirichlet boundary condition, however, the Neumann boundary condition in the quantum algorithm cannot exceed a second-order Laplacian approximation. Moreover, the anisotropy error is inherent to the lattice geometry. In this work, we propose a quantum wave equation solver on a hexagonal grid, which exhibits intrinsic grid dispersion comparable to that of a fourth-order accurate method on a rectangular grid and provides a quadratic improvement in the anisotropy measures. We show that the graph Laplacian on a hexagonal grid embedding the Neumann boundary condition is a bidirected graph. To make it suitable for use as a system Hamiltonian, a symmetrization and factorization based on the asymmetric adjacency matrix is proposed. Dispersion relations for quantum algorithms solving the wave equation on different lattices are derived and compared. The algorithms are analyzed as a limiting case of Yee's finite-difference time-domain method in the context of electromagnetic wave propagation.

关键词： Propagation Laplace equations quantum algorithm Boundary conditions Mathematical models Dispersion Finite difference methods Electromagnetics finite difference methods hexagonal lattices numerical dispersion numerical modeling radio wave propagation quantum algorithms time domain analysis

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights

引用

quantum INFORMATION PROCESSING 2011年第2期10卷 177-188页

作者： Choi, Byung-Soo Braunstein, Samuel L. Ewha Womans Univ Dept Elect Engn Seoul South Korea Univ York Dept Comp Sci York YO10 5DD N Yorkshire England

As one of the applications of Grover search, an exact quantum algorithm for the symmetric weight decision problem of a Boolean function has been proposed recently. Although the proposed method shows a quadratic speedup over the classical approach, it only applies to the symmetric case of a Boolean function whose weight is one of the pair {0 < w(1) < w(2) < 1, w(1) + w(2) = 1}. In this article, we generalize this algorithm in two ways. Firstly, we propose a quantum algorithm for the more general asymmetric case where {0 < w(1) < w(2) < 1}. This algorithm is exact and computationally optimal. Secondly, we build on this to exactly solve the multiple weight decision problem for a Boolean function whose weight as one of {0 < w(1) < w(2) < center dot center dot center dot < w(m) < 1}. This extended algorithm continues to show a quantum advantage over classical methods. Thirdly, we compare the proposed algorithm with the quantum counting method. For the case with two weights, the proposed algorithm shows slightly lower complexity. For the multiple weight case, the two approaches show different performance depending on the number of weights and the number of solutions. For smaller number of weights and larger number of solutions, theweight decision algorithm can show better performance than the quantum counting method. Finally, we discuss the relationship between the weight decision problem and the quantum state discrimination problem.

关键词： quantum algorithm Generalized weight decision problem Query complexity

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for total least squares data fitting

引用

PHYSICS LETTERS A 2019年第19期383卷 2235-2240页

作者： Wang, Hefeng Xiang, Hua Xi An Jiao Tong Univ Sch Sci Dept Appl Phys Xian 710049 Shaanxi Peoples R China Shaanxi Prov Key Lab Quantum Informat & Quantum O Xian 710049 Shaanxi Peoples R China Wuhan Univ Sch Math & Stat Wuhan 430072 Hubei Peoples R China

The total least squares (TLS) method is widely used in data-fitting. Compared with the least squares fitting method, the TLS fitting takes into account not only observation errors, but also errors from the measurement matrix of the variables. In this work, the TLS problem is transformed to finding the ground state of a Hamiltonian matrix. We propose quantum algorithms for solving this problem based on quantum simulation of resonant transitions. Our algorithms can achieve at least polynomial speedup over the known classical algorithms. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Total least squares quantum simulation quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for Triangle Finding in Sparse Graphs

引用

algorithmICA 2017年第3期79卷 941-959页

作者： Le Gall, Francois Nakajima, Shogo Univ Tokyo Dept Comp Sci Grad Sch Informat Sci & Technol Tokyo Japan

This paper presents a quantum algorithm for triangle finding over sparse graphs that improves over the previous best quantum algorithm for this task by Buhrman et al. (SIAM J Comput 34(6):1324-1330, 2005). Our algorithm is based on the recent (O) over tilde (n(5/4))-query algorithm given by Le Gall (Proceedings of the 55th IEEE annual symposium on foundations of computer science, pp 216-225, 2014) for triangle finding over dense graphs (here n denotes the number of vertices in the graph). We show in particular that triangle finding can be solved with O(n(5/4-epsilon)) queries for some constant epsilon > 0 whenever the graph has at most O(n(2-c))edges for some constant c > 0.

关键词： quantum algorithm quantum walk Triangle finding

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm FOR MATRIX FUNCTIONS BY CAUCHY'S INTEGRAL FORMULA

引用

quantum INFORMATION & COMPUTATION 2020年第1-2期20卷 14-36页

作者： Takahira, Souichi Ohashi, Asuka Sogabe, Tomohiro Usuda, Tsuyoshi Sasaki Aichi Prefectural Univ Grad Sch Informat Sci & Technol 1522-3 Ibaragabasama Nagakute Aichi 4801198 Japan Ritsumeikan Univ Coll Sci & Engn 1-1-1 Noji Higashi Kusatsu Shiga 5258577 Japan Nagoya Univ Grad Sch Engn Chikusa Ku Furo Cho Nagoya Aichi 4648603 Japan

For matrix A, vector b and function f, the computation of vector f (A)b arises in many scientific computing applications. We consider the problem of obtaining quantum state vertical bar f > corresponding to vector f (A)b. There is a quantum algorithm to compute state vertical bar f > using eigenvalue estimation that uses phase estimation and Hamiltonian simulation e(iAt). However, the algorithm based on eigenvalue estimation needs poly(1/epsilon) runtime, where epsilon is the desired accuracy of the output state. Moreover, if matrix A is not Hermitian, e(iAt) is not unitary and we cannot run eigenvalue estimation. In this paper, we propose a quantum algorithm that uses Cauchy's integral formula and the trapezoidal rule as an approach that avoids eigenvalue estimation. We show that the runtime of the algorithm is poly(log(1/epsilon) and the algorithm outputs state vertical bar f > even if A is not Hermitian.

关键词： quantum algorithm Matrix functions HHL algorithm Cauchy's integral formula

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for K-Nearest Neighbors Classification Based on the Metric of Hamming Distance

引用

INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS 2017年第11期56卷 3496-3507页

作者： Ruan, Yue Xue, Xiling Liu, Heng Tan, Jianing Li, Xi Anhui Univ Technol Sch Comp Sci & Technol Maanshan 243005 Peoples R China Southeast Univ Minist Educ Key Lab Comp Network & Informat Integrat Nanjing 210096 Jiangsu Peoples R China Southeast Univ Sch Comp Sci & Engn Nanjing 210096 Jiangsu Peoples R China

K-nearest neighbors (KNN) algorithm is a common algorithm used for classification, and also a sub-routine in various complicated machine learning tasks. In this paper, we presented a quantum algorithm (QKNN) for implementing this algorithm based on the metric of Hamming distance. We put forward a quantum circuit for computing Hamming distance between testing sample and each feature vector in the training set. Taking advantage of this method, we realized a good analog for classical KNN algorithm by setting a distance threshold value t to select k - n e a r e s t neighbors. As a result, QKNN achieves O(n (3)) performance which is only relevant to the dimension of feature vectors and high classification accuracy, outperforms Llyod's algorithm (Lloyd et al. 2013) and Wiebe's algorithm (Wiebe et al. 2014).

关键词： quantum algorithm K-nearest neighbors algorithm Hamming distance Classification Machine learning

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for the multicollision problem

引用

THEORETICAL COMPUTER SCIENCE 2020年 842卷 100-117页

作者： Hosoyamada, Akinori Sasaki, Yu Tani, Seiichiro Xagawa, Keita NTT Corp NTT Secure Platform Labs 3-9-11 Midori Cho Musashino Tokyo 1808585 Japan Nagoya Univ Dept Informat & Commun Engn Chikusa Ku Furo Cho Nagoya Aichi 4648603 Japan NTT Corp NTT Commun Sci Labs 3-1 Morinosato Wakamiya Atsugi Kanagawa 2430198 Japan

The current paper presents a new quantum algorithm for finding multicollisions, often denoted by l-collisions, where an l-collision for a function is a set of L distinct inputs that are mapped by the function to the same value. In cryptology, it is important to study how many queries are required to find an l-collision for a random function of which domain is larger than its range. However, the problem of finding l-collisions for random functions has not received much attention in the quantum setting. The tight bound of quantum query complexity for finding a 2-collisions of a random function has been revealed to be Theta(N-1/3), where N is the size of the range of the function, but neither the lower nor upper bounds are known for general l-collisions. The paper first integrates the results from existing research to derive several new observations, e.g., l-collisions can be generated only with O(N-1/2) quantum queries for any integer constant L. It then provides a quantum algorithm that finds an l-collision for a random function with the average quantum query complexity of O(N(2l-1 -1)/(2(l)-1)), which matches the tight bound of Theta(N-1/3) for l = 2 and improves upon the known bounds, including the above simple bound of O(N-1/2). More generally, the algorithm achieves the average quantum query complexity of O(c(N).N(2l-1 -1)/(2l-1)), and runs over (O) over tilde (c(N).N(2l-1 -1)/2l-1)) qubits in a (O) over tilde (c(N).N(2l-1 -1)/2l-1)) expected time for a random function F : X -> Y such that vertical bar X vertical bar >= l . vertical bar Y vertical bar/c(N) for any 1 <= c(N) is an element of o (N1/(2l-1)), where it is assumed that QRAM is available. With the same query complexity, it is actually able to find a multiclaw for random functions, which is harder to find than a multicollision. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Post-quantum cryptography quantum algorithm Multiclaw Multicollision

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for Solving the Continuous Hidden Symmetry Subgroup Problem

引用

IEEE ACCESS 2021年 9卷 93248-93254页

作者： Bae, Eunok Lee, Soojoon Kyung Hee Univ Dept Math Seoul 02447 South Korea Kyung Hee Univ Res Inst Basic Sci Seoul 02447 South Korea

quantum computers are expected to be able to outperform classical computers. In fact, some computational problems such as integer factorization can be solved on quantum computers substantially faster than classical computers. Interestingly, these problems can be cast in a framework of the hidden symmetry subgroup problem. However, only a few of quantum algorithms for effciently solving this problem have been known, and the approaches used in all previous results can be applied to particular groups with specific group actions. In this paper, we introduce new technique for solving the hidden symmetry subgroup problem which can be applicable for any groups and any group actions with a certain condition. In addition, we define the continuous hidden symmetry subgroup problem on a group by employing a continuous oracle function, and prove that if the group is a metric space and the group action satisfies some condition, then the continuous hidden symmetry subgroup problem can be efficiently reduced to the continuous hidden subgroup problem. In particular, we show that there exists an efficient quantum algorithm to solve the continuous hidden symmetry subgroup problem on R-n, while it has not yet been shown that the original hidden symmetry subgroup problem on R-n can be efficiently solved by a quantum computer.

关键词： quantum algorithm continuous hidden symmetry subgroup problem hidden symmetry subgroup problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：