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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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)

来源：评论

学校读者我要写书评

暂无评论

Windowed quantum Phase Estimation: Signal Processing Approach to a quantum algorithm

Windowed Quantum Phase Estimation: Signal Processing Approac...

引用

International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Xue Wen Samsung Research China Beijing

ISBN: (数字)9798350368741

ISBN: (纸本)9798350368758

quantum phase estimation (QPE) is a key ingredient to some of the most important results of quantum computing. In this paper we examine the QPE algorithm through the looking glass of signal processing. This perspective helps to reveal a relation between the distribution of quantum phase estimates and the shape of the discrete Fourier transform (DFT) of a pure complex sinusoid. Guided by spectral shaping theory, we design a class of quantum circuits that are the quantum equivalents to classical windowing operators, for a family of window functions that have compact support in the DFT. These circuits have complexity linear in the number of target qubits, strictly lower than QPE itself. Using these circuits we are able to reshape QPE's performance characteristics. In particular, the asymptotic marginal cost for 2x reduction in fail rate (2x improvement in reliability) is reduced from one qubit to 1/3 qubit or lower, which can help reduce the qubit budget for a preset accuracy-reliability target, especially in high-reliability scenarios. This makes a demonstration of the value of signal processing principles in designing quantum algorithms.

关键词： quantum algorithm Shape Qubit Discrete Fourier transforms Phase estimation Signal processing algorithms quantum mechanics Signal processing Windows Speech processing

来源：评论

学校读者我要写书评

暂无评论

Two-Step quantum Search algorithm for Solving Traveling Salesman Problems

IEEE TRANSACTIONS ON QUANTUM ENGINEERING

引用

IEEE TRANSACTIONS ON quantum ENGINEERING 2025年第1期6卷 1-12页

作者： Sato, Rei Gordon, Cui Saito, Kazuhiro Kawashima, Hideyuki Nikuni, Tetsuro Watabe, Shohei KDDI Res Inc Quantum Comp Grp Fujimino 3568502 Japan Tokyo Univ Sci Dept Phys Tokyo 1628601 Japan Keio Univ Fac Environm & Informat Studies Fujisawa 2520882 Japan Shibaura Inst Technol Fac Engn Comp Sci & Engn Tokyo 1358548 Japan

quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state-an equal superposition of all feasible solutions satisfying the problem's constraints-is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, we propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher order unconstrained binary optimization representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.

关键词： Costs Urban areas Optimization Search problems Encoding quantum circuit Complexity theory Traveling salesman problems quantum algorithm Heuristic algorithms Grover's algorithm quantum search algorithms traveling salesman problems (TSPs)

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：