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

quantum Hamiltonian Descent for Non-smooth Optimization

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Leng, Jiaqi Zheng, Yufan Jia, Zhiyuan Fan, Lei Zhao, Chaoyue Peng, Yuxiang Wu, Xiaodi Simons Institute for the Theory of Computing University of California Berkeley United States Department of Mathematics University of California Berkeley United States Department of Computer Science University of Maryland College Park United States Joint Center for Quantum Information and Computer Science University of Maryland United States Department of Applied Mathematics University of Washington United States Department of Engineering Technology University of Houston United States Department of Electrical and Computer Engineering University of Houston United States Department of Industrial and Systems Engineering University of Washington United States Artephi Computing Inc United States

Non-smooth optimization models play a fundamental role in various disciplines, including engineering, science, management, and finance. However, classical algorithms for solving such models often struggle with convergence speed, scalability, and parameter tuning, particularly in high-dimensional and non-convex settings. In this paper, we explore how quantum mechanics can be leveraged to overcome these limitations. Specifically, we investigate the theoretical properties of the quantum Hamiltonian Descent (QHD) algorithm for non-smooth optimization in both continuous and discrete time. First, we propose continuous-time variants of the general QHD algorithm and establish their global convergence and convergence rate for non-smooth convex and strongly convex problems through a novel Lyapunov function design. Furthermore, we prove the finite-time global convergence of continuous-time QHD for non-smooth non-convex problems under mild conditions (i.e., locally Lipschitz). In addition, we propose discrete-time QHD, a fully digitized implementation of QHD via operator splitting (i.e., product formula). We find that discrete-time QHD exhibits similar convergence properties even with large time steps. Finally, numerical experiments validate our theoretical findings and demonstrate the computational advantages of QHD over classical non-smooth non-convex optimization algorithms. Copyright © 2025, The Authors. All rights reserved.

关键词： Continuous time systems

State Permutation Control in Non-Hermitian Multiqubit Systems with Suppressed Non-Adiabatic Transitions

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Arkhipov, Ievgen I. Lewalle, Philippe Nori, Franco Özdemir, Şahin K. Whaley, K. Birgitta Joint Laboratory of Optics Palacký University Institute of Physics of CAS Faculty of Science Palacký University 17. listopadu 12 Olomouc771 46 Czech Republic Department of Chemistry University of California BerkeleyCA94720 United States Berkeley Center for Quantum Information and Computation BerkeleyCA94720 United States Theoretical Quantum Physics Laboratory Cluster for Pioneering Research RIKEN Saitama Wako-shi351-0198 Japan Quantum Information Physics Theory Research Team Quantum Computing Center RIKEN Wakoshi Saitama351-0198 Japan Physics Department The University of Michigan Ann ArborMI48109-1040 United States Department of Electrical and Computer Engineering Saint Louis University St. LouisMO63103 United States

Non-Hermitian systems have been at the focus of intense research for over a decade, partly due to their nontrivial energy topology formed by intersecting Riemann manifolds with branch points known as exceptional points (EPs). This spectral property can be exploited, e.g., to achieve controlled state permutations that are necessary for implementing a wide class of classical and quantum information protocols. However, the imaginary spectra of typical non-Hermitian systems lead to instabilities and breakdown of adiabaticity, which impedes the practical use of EP-induced energy topologies in quantum information protocols that explicitly rely on symmetric state flips. On the other hand, techniques that help to suppress non-adiabatic transitions in non-Hermitian systems have also been developed, but these advances have so far been limited to single qubits. In this work, we address this long-standing problem by introducing a model of interacting qubits governed by an effective non-Hermitian Hamiltonian that hosts EPs and possesses a completely real energy spectrum. We demonstrate that such non-Hermitian Hamiltonians enable realization of permutation groups in the multi-qubit eigenspace. Our findings indicate that, contrary to previous beliefs, non-Hermiticity can be utilized to achieve controlled state permutations in time-modulated multiqubit systems, thus paving the way for the advancement and development of novel quantum information protocols. Copyright © 2025, The Authors. All rights reserved.

关键词： Qubits

Characterization of Exact One-Query quantum Algorithms for Partial Boolean Functions

学校读者我要写书评

暂无评论

Journal of computer Science & Technology 2023年第6期38卷 1423-1430页

作者：叶泽坤李绿周 Institute of Quantum Computing and Computer Theory School of Computer Science and EngineeringSun Yat-sen UniversityGuangzhou 510006China Ministry of Education Key Laboratory of Machine Intelligence and Advanced Computing Sun Yat-sen UniversityGuangzhou 510006China

The query model(or black-box model)has attracted much attention from the communities of both classical and quantum ***,quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical *** the history of quantum algorithms,the Deutsch algorithm and the Deutsch-Jozsa algorithm play a fundamental role and both are exact one-query quantum *** leads us to con-sider the problem:what functions can be computed by exact one-query quantum algorithms?This problem has been ad-dressed in the literature for total Boolean functions and symmetric partial Boolean functions,but is still open for general partial Boolean ***,in this paper,we continue to characterize the computational power of exact one-query quantum algorithms for general partial Boolean ***,we present several necessary and sufficient conditions for a partial Boolean function to be computed by exact one-query quantum ***,inspired by these conditions,we discover some new representative functions that can be computed by exact one-query quantum algorithms but have an essential difference from the already known ***,it is worth pointing out that before our work,the known func-tions that can be computed by exact one-query quantum algorithms are all symmetric functions and the quantum algo-rithm used is essentially the Deutsch-Jozsa algorithm,whereas the functions discovered in this paper are generally asym-metric and new algorithms to compute these functions are ***,this expands the class of functions that can be computed by exact one-query quantum algorithms.

关键词： quantum computing quantum query complexity quantum algorithm

Arbitrary state creation via controlled measurement

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zenchuk, Alexander I. Qi, Wentao Wu, Junde Federal Research Center of Problems of Chemical Physics and Medicinal Chemistry RAS Moscow reg. Chernogolovka142432 Russia Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China School of Mathematical Sciences Zhejiang University Hangzhou310027 China

We propose the algorithm for creating an arbitrary pure quantum superposition state with required accuracy of encoding the amplitudes and phases of this state. The algorithm uses controlled measurement of the ancilla state to avoid the problem of small probability of detecting the required ancilla state. This algorithm can be a subroutine generating the required input state in various algorithms, in particular, in matrix-manipulation algorithms developed earlier. © 2025, CC BY.

关键词：

Robust quantum walk search without knowing the number of marked vertices

学校读者我要写书评

暂无评论

Physical Review A 2022年第5期106卷 052207-052207页

作者： Yongzhen Xu Delong Zhang Lvzhou Li Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou 510006 China

There has been a very large body of research on searching a marked vertex on a graph based on quantum walks, and Grover's algorithm can be regarded as a quantum walk-based search algorithm on a special graph. However, the existing quantum walk-based search algorithms suffer severely from the soufflé problem, which mainly means that the success probability of finding a marked vertex could shrink dramatically, even to zero, when the number of search steps is greater than the right one, thus heavily reducing the robustness and practicability of the algorithm. Surprisingly, while the soufflé problem of Grover's algorithm has attracted enough attention, how to address this problem for general quantum walk-based search algorithms is missing in the literature. Here we initiate the study of overcoming the soufflé problem for quantum walk-based search algorithms by presenting a quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup. In this framework, for any adjustable parameter ε, the quantum algorithm can find a marked vertex on an N-vertex complete bipartite graph with probability at least 1−ε, whenever the number of search steps h satisfies h≥ln(2ε)N+1. Note that the algorithm need not know the exact number of marked vertices. Consequently, we obtain quantum search algorithms with stronger robustness and practicability.

关键词： quantum algorithms quantum walks

Distributed exact Grover’s algorithm

学校读者我要写书评

暂无评论

Frontiers of physics 2023年第5期18卷 255-279页

作者： Xu Zhou Daowen Qiu Le Luo Institute of Quantum Computing and Computer Theory School of Computer Science and EngineeringSun Yat-sen UniversityGuangzhou 510006China The Guangdong Key Laboratory of Information Security Technology Sun Yat-sen UniversityGuangzhou 510006China School of Physics and Astronomy Sun Yat-sen UniversityZhuhai 519082China QUDOOR Co Ltd.Beijing 100089China

Distributed quantum computation has gained extensive *** this paper,we consider a search problem that includes only one target item in the unordered *** that,we propose a distributed exact Grover’s algorithm(DEGA),which decomposes the original search problem into■n/2■***,(i)our algorithm is as exact as the modified version of Grover’s algorithm by Long,which means the theoretical probability of finding the objective state is 100%;(ii)the actual depth of our circuit is 8(n mod 2)+9,which is less than the circuit depths of the original and modified Grover’s algorithms,1+8■π/4√2^(n)■and 9+8■π/4√2^(n)-1/2■,*** only depends on the parity of n,and it is not deepened as n increases;(iii)we provide particular situations of the DEGA on Mindquantum(a quantum software)to demonstrate the practicality and validity of our *** our circuit is shallower,it will be more resistant to the depolarization channel noise.

关键词： distributed quantum computation search problem distributed exact Grover’s algorithm(DEGA) Mindquantum the depolarization channel noise

Circuit Lower Bounds for Low-Energy States of quantum Code Hamiltonians 13

学校读者我要写书评

暂无评论

Circuit Lower Bounds for Low-Energy States of Quantum Code H...

13th Innovations in Theoretical computer Science Conference, ITCS 2022

作者： Anshu, Anurag Nirkhe, Chinmay Simons Institute for the Theory of Computing BerkeleyCA United States Challenge Institute for Quantum Computation University of California BerkeleyCA United States Electrical Engineering and Computer Sciences University of California BerkeleyCA United States

ISBN: (纸本)9783959772174

The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings [27] - which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states - identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n). Such codes are known to exist and are not necessarily locally-testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems. © Anurag Anshu and Chinmay Nirkhe;licensed under Creative Commons License CC-BY 4.0

关键词： Hamiltonians

Concise and Efficient quantum Algorithms for Distribution Closeness Testing

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Li, Lvzhou Luo, Jingquan Institute of Quantum Computing and Computer Theory School of Computer and Engineering Sun Yat-sen University China

We study the impact of quantum computation on the fundamental problem of testing the property of distributions. In particular, we focus on testing whether two unknown classical distributions are close or far enough, and propose the currently best quantum algorithms for this problem under the metrics of l1-distance and l2-distance. Compared with the latest results given in [9] which relied on the technique of quantum singular value transformation (QSVT), our algorithms not only have lower complexity, but also are more concise. © 2023, CC BY.

关键词： quantum theory

Playing Mastermind on quantum computers

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Li, Lvzhou Luo, Jingquan Xu, Yongzhen Institute of Quantum Computing and Computer Theory School of Computer and Engineering Sun Yat-sen University China

From the 1970s up to now, the classic two-player game, Mastermind, has attracted plenty of attention, not only from the public as a popular game, but also from the academic community as a scientific issue. Mastermind with n positions and k colors is formally described as follows. The codemaker privately chooses a secret s ∈ [k]n, and the codebreaker want to determine s in as few queries like fs(x) as possible to the codemaker. fs(x) is called a black-peg query if fs(x) = Bs(x), and a black-white-peg query if fs(x) = {Bs(x), Ws(x)}, where Bs(x) indicates the number of positions where s and x coincide and Ws(x) indicates the number of right colors but being in the wrong position. The complexity of a strategy is measured by the number of queries used. In this work we study playing Mastermind on quantum computers in both non-adaptive and adaptive settings, obtaining efficient quantum algorithms which are all exact (i.e., return the correct result with certainty) and show huge quantum speedups. The contributions are as follows. (i) Based on the discovery of new structure information, we construct two non-adaptive quantum algorithms which determine the secret with certainty and consume k − 1 and at most 2[k/3] black-peg queries, respectively. (ii) If adaptive strategies are admitted, a more efficient exact quantum algorithm is obtained, which consumes only O(√k) black-peg queries. Furthermore, we prove that any quantum algorithm requires at least Ω(√k) black-peg queries. (iii) When black-white-peg queries are allowed, we propose an adaptive exact quantum algorithm with (Equation presented) queries, where Cs is the set of colors occupied by s. This algorithm breaks through the lower bound Ω(√k) when n ≤ k ≤ n2. (iv) Technically, we develop a three-step framework for designing quantum algorithms for the general string learning problem, which not only allows huge quantum speedups on playing Mastermind, but also may shed light on exploring quantum speedups for other string le

关键词： Color