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

quantum algorithm for minimum dominating set problem with circuit design

Chinese Physics B 2024年第2期33卷 178-188页

作者：张皓颖王绍轩刘新建沈颖童王玉坤 Beijing Key Laboratory of Petroleum Data Mining China University of PetroleumBeijing 102249China State Key Laboratory of Cryptology P.O.Box 5159Beijing 100878China

Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum *** are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete *** paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected *** expedite the search process,a quantum algorithm employing Grover’s search is ***,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover’s search ***,a swap test method is introduced to ascertain the number of iterations *** oracle,diffusion operators,and swap test are designed with achievable quantum *** query complexity is O(1.414^(n))and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.

关键词： quantum algorithm circuit design minimum dominating set

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for finding the optimal variable ordering for binary decision diagrams

引用

THEORETICAL COMPUTER SCIENCE 2025年 1041卷

作者： Tani, Seiichiro NTT Corp NTT Commun Sci Labs 3-1 Morinosato Wakamiya Atsugi 2430198 Japan Waseda Univ 1-6-1 Nishiwaseda Tokyo Tokyo 1698050 Japan

An ordered binary decision diagram (OBDD) is a directed acyclic graph representing a Boolean function. Since OBDDs have many nice properties as data structures, they have been extensively studied for decades in theoretical and practical fields, such as VLSI (Very Large Scale Integration) design, formal verification, machine learning, and combinatorial problems. Arguably, the most crucial problem in using OBDDs is that they may vary exponentially in size depending on their variable ordering (i.e., the order in which the variables are to be read) when they represent the same function. Indeed, it is NP-hard to find an optimal variable ordering that minimizes an OBDD for a given function. Friedman and Supowit provided a clever deterministic algorithm with time/space complexity O & lowast;(3 degrees), where degrees is the number of variables of the function, which is much better than the trivial brute-force bound O & lowast;(degrees!2 degrees). This paper shows that a further speedup is possible with quantum computers by presenting a quantum algorithm that produces a minimum OBDD together with the corresponding variable ordering in O & lowast;(2.77286 degrees) time and space with an exponentially small error probability. Moreover, this algorithm can be adapted to constructing other minimum decision diagrams, such as zero-suppressed BDDs (ZBDDs or ZDDs).

关键词： OBDD Decision diagram quantum algorithm quantum computing

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for Optimization and Polynomial System Solving over Finite Field and Application to Cryptanalysis

引用

JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY 2025年 1-32页

作者： Chen, Yu-Ao Gao, Xiao-Shan Yuan, Chun-Ming Chinese Acad Sci Acad Math & Syst Sci KLMM Beijing 100190 Peoples R China Hong Kong Univ Sci & Technol Guangzhou Thrust Artificial Intelligence Informat Hub Guangzhou 511453 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China

In this paper, the authors give quantum algorithms for two fundamental computation problems: Solving polynomial systems over finite fields and optimization where the arguments of the objective function and constraints take values from a finite field or a bounded interval of integers. The quantum algorithms can solve these problems with any given success probability and have polynomial runtime complexities in the size of the input, the degree of the inequality constraints, and the condition number of the associated matrices of the problem. So, the authors achieve exponential speedup for these problems when their condition numbers are small. As applications, quantum algorithms are given to three basic computational problems in cryptography: The short integer solution problem, the shortest vector problem, the polynomial system with noise problem, and cryptanalysis for the lattice-based NTRU cryptosystem. It is shown that these problems and NTRU can against quantum computer attacks only if their condition numbers are large, so the condition number could be used as a new criterion for lattice-based post-quantum cryptosystems.

关键词： Cryptanalysis of NTRU finite field integer programming polynomial system solving polynomial system with noise quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

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 matrix logarithm by integral formula

引用

quantum INFORMATION PROCESSING 2023年第1期22卷 1-25页

作者： Wang, Yatian Xiang, Hua Zhang, Songling Wuhan Univ Sch Math & Stat Wuhan 430072 Peoples R China Wuhan Univ Hubei Key Lab Computat Sci Wuhan 430072 Peoples R China

In scientific computing, one can find a wide application of the matrix-vector product f (A)b. Recently, a quantum algorithm that computes the state | f > corresponding to f (A)b has been proposed in Takahira et al. (quantum Inf Comput 20(1/2):14-36, 2020). However, this important algorithm can not be directly applied to the matrix logarithm, which is one of the significant matrix functions. In this paper, we propose an original quantum algorithm to compute the state | f > = log(A)|b >/|| log(A)|b >/||, via the integral representation of log(A) and the Gauss-Legendre quadrature rule, using LCU method and block-encoding technique as subroutines.

关键词： quantum algorithm Matrix logarithm Gauss-Legendre

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for Position Weight Matrix Matching

IEEE TRANSACTIONS ON QUANTUM ENGINEERING

引用

IEEE TRANSACTIONS ON quantum ENGINEERING 2023年第1期4卷 1页

作者： Miyamoto, Koichi Yamamoto, Naoki Sakakibara, Yasubumi Osaka Univ Ctr Quantum Informat & Quantum Biol Toyonaka 5600043 Japan Keio Univ Dept Appl Phys & Physico Informat Yokohama 2238521 Japan Keio Univ Quantum Comp Ctr Yokohama 2238521 Japan Keio Univ Dept Biosci & Informat Yokohama 2238521 Japan

In this article, we propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence, such as DNA and protein that have high scores defined by the PWM and are, thus, of informational importance related to biological function. The two proposed algorithms, the naive iteration method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence and the PWM. The former uses quantum amplitude amplification (QAA) for sequence motif search, resulting in the query complexity scaling on the sequence length n, the sequence motif length m, and the number of the PWMs K as O(m root Kn), which means speedup over existing classical algorithms with respect to n and K. The latter also uses QAA and, further, quantum Monte Carlo integration for segment score calculation, instead of iteratively operating quantum circuits for arithmetic in the naive iteration method;then, it provides the additional speedup with respect to m in some situation. As a drawback, these algorithms use quantum random access memories, and their initialization takes O(n) time. Nevertheless, our algorithms keep the advantage especially when we search matches in a sequence for many PWMs in parallel

关键词： Pulse width modulation quantum algorithm Complexity theory DNA Proteins Biology Bioinformatics position weight matrix (PWM) matching quantum algorithm quantum amplitude amplification (QAA) quantum Monte Carlo integration (QMCI)

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for neighborhood preserving embedding

引用

Chinese Physics B 2022年第6期31卷 192-203页

作者： Shi-Jie Pan Lin-Chun Wan Hai-Ling Liu Yu-Sen Wu Su-Juan Qin Qiao-Yan Wen Fei Gao 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

Neighborhood preserving embedding(NPE)is an important linear dimensionality reduction technique that aims at preserving the local manifold *** contains three steps,i.e.,finding the nearest neighbors of each data point,constructing the weight matrix,and obtaining the transformation *** et *** a variational quantum algorithm(VQA)for NPE[***.A 101032323(2020)].The algorithm consists of three quantum sub-algorithms,corresponding to the three steps of NPE,and was expected to have an exponential speedup on the dimensionality ***,the algorithm has two disadvantages:(i)It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one.(ii)Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a *** this paper,we propose a complete quantum algorithm for NPE,in which we redesign the three sub-algorithms and give a rigorous complexity *** is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm,and achieve a significant speedup compared to Liang et al.’s algorithm even without considering the complexity of the VQA.

关键词： quantum algorithm quantum machine learning amplitude amplification

来源：评论

学校读者我要写书评

暂无评论

Derandomization of quantum algorithm for triangle finding

引用

INFORMATION AND COMPUTATION 2025年 304卷

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

Derandomization is the process of taking a randomized algorithm and turning it into a deterministic algorithm, which has attracted great attention in classical computing. In quantum computing, it is challenging and intriguing to derandomize quantum algorithms, due to the inherent randomness of quantum mechanics. The significance of derandomizing quantum algorithms lies not only in theoretically proving that the success probability can essentially be 1 without sacrificing quantum speedups, but also in experimentally improving the success rate when the algorithm is implemented on a real quantum computer. In this paper, we focus on derandomizing quantum algorithms for the triangle sum problem (including the famous triangle finding problem as a special case), which asks to find a triangle in an edge-weighted graph with n vertices, such that its edges sum up to a given weight. We show that when the graph is promised to contain at most one target triangle, there exists a deterministic quantum algorithm that either finds the triangle if it exists or outputs "no triangle" if none exists. It makes O(n9/7) queries to the edge weight matrix oracle, and thus has the same complexity as the state-of-the-art boundederror quantum algorithm. To achieve this derandomization, we make full use of several techniques: nested quantum walk with quantum data structure, deterministic quantum search with adjustable parameters, and dimensional reduction of quantum walk search on Johnson graph. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Triangle finding Triangle sum problem Discrete-time quantum walk quantum algorithm quantum query complexity

来源：评论

学校读者我要写书评

暂无评论

quantum algorithm for copula-based risk aggregation using orthogonal series density estimation 5

Quantum algorithm for copula-based risk aggregation using or...

引用

2024 International Conference on quantum Computing and Engineering

作者： Mori, Hitomi Miyamoto, Koichi Osaka Univ Grad Sch Engn Sci Toyonaka Osaka Japan Osaka Univ Ctr Quantum Informat & Quantum Biol Toyonaka Osaka Japan

ISBN: (纸本)9798331541378

quantum Monte Carlo integration (QMCI) provides a quadratic speed-up over its classical counterpart, and its applications have been investigated in various fields, including finance. This paper considers its application to risk aggregation, one of the most important numerical tasks in financial risk management. Risk aggregation combines several risk variables and quantifies the total amount of risk, taking into account the correlation among them. For this task, there exists a useful tool called copula, with which the joint distribution can be generated from marginal distributions with a flexible correlation structure. Classically, the copula-based method utilizes sampling of risk variables. However, this procedure is not directly applicable to the quantum setting, where sampled values are not stored as classical data, and thus no efficient quantum algorithm is known. In this paper, we introduce a quantum algorithm for copula-based risk aggregation that is compatible with QMCI. In our algorithm, we first estimate each marginal distribution as a series of orthogonal functions, where the coefficients can be calculated with QMCI. Then, by plugging the marginal distributions into the copula and obtaining the joint distribution, we estimate risk measures using QMCI again. With this algorithm, nearly quadratic quantum speed-up can be obtained for sufficiently smooth marginal distributions.

关键词： quantum algorithm quantum Monte Carlo integration Finance Risk aggregation

来源：评论

学校读者我要写书评

暂无评论

A probabilistic quantum algorithm for imaginary-time evolution based on Taylor expansion

引用

EPJ quantum TECHNOLOGY 2025年第1期12卷 1-22页

作者： Yi, Xin Huo, Jiacheng Liu, Guanhua Fan, Ling Zhang, Ru Cao, Cong China Mobile Res Inst Future Res Lab Beijing 100053 Peoples R China Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China Beijing Jiaotong Univ Sch Transportat Beijing 100044 Peoples R China Beijing Univ Posts & Telecommun Sch Elect Engn Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Beijing Key Lab Space Ground Interconnect & Conver Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun State Key Lab Informat Photon & Opt Commun Beijing 100876 Peoples R China

Imaginary-time evolution is a powerful tool for obtaining the ground state of a quantum system, but the complexity of classical algorithms designed for simulating imaginary-time evolution will increase significantly as the size of the quantum system becomes larger. Here, a probabilistic quantum algorithm based on Taylor expansion for implementing imaginary-time evolution is introduced. For Hamiltonians composed of Pauli product terms, the quantum circuit requires only a single ancillary qubit and is exclusively constructed using elementary single-qubit and two-qubit gates. Furthermore, similar principles are used to extend the algorithm to the case where the Hamiltonian takes a more general form. The algorithm only requires negligible precomputed numerical calculations, without the need for complex classical pre-mathematical calculations or optimization loops. We demonstrate the algorithm by solving the ground state energy of hydrogen molecules and Heisenberg Hamiltonians. Moreover, we conducted experiments on real quantum computers through the quantum cloud platform to find the ground state energy of Heisenberg Hamiltonians. Our work extends the methods for realizing imaginary-time evolution on quantum computers, and our algorithm exhibits potential for implementation on near-term quantum devices, particularly when the Hamiltonian consists of Pauli product terms.

关键词： quantum algorithm Linear combination of unitaries Imaginary-time evolution Ground state simulation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：