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

Deterministic Algorithms for the Hidden Subgroup Problem

学校读者我要写书评

暂无评论

SSRN

SSRN 2022年

作者： Ye, Zekun Li, Lvzhou Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China Ministry of Education Key Laboratory of Machine Intelligence and Advanced Computing Sun Yat-sen University Guangzhou510006 China

We consider deterministic algorithms for the well-known hidden subgroup problem (HSP): for a finite group G and a finite set X, given a function f : G → X and the promise that for any (Formula Presented) for a subgroup H ≤ G, the goal of the decision version is to determine whether H is trivial, and the goal of the search version is to find H. An algorithm for the problem should query f(g) for g ∈ G at least as possible. Nayak [? ] asked whether there exist deterministic algorithms with (Formula Presented) query complexity for HSP. We answer this problem completely by proving the following results, which also extend the main results of Ref. [? ], since here the algorithms do not rely on any prior knowledge of H. (i) When G is a general finite Abelian group, there exists an algorithm with (Formula Presented) queries to decide the triviality of H and an algorithm to find H with (Formula Presented) queries.(ii) In general, there is no deterministic algorithm for the search version of HSP with query complexity of (Formula Presented), since there exists an instance of HSP that needs (Formula Presented) queries to find H. f(x) is said to be (Formula Presented) if for every positive constant C, there exists a positive constant N such that for (Formula Presented), which means g is a strict lower bound for f.} On the other hand, there exist instances of HSP with query complexity far smaller than (Formula Presented), whose query complexity is (Formula Presented) and even O(1). © 2022, The Authors. All rights reserved.

关键词： Computational complexity

Small correlation is sufficient for optimal noisy quantum metrology

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yin, Chao Albert, Victor V. Zhou, Sisi Department of Physics Center for Theory of Quantum Matter University of Colorado BoulderCO80309 United States Joint Center for Quantum Information and Computer Science NIST University of Maryland College ParkMD United States Perimeter Institute for Theoretical Physics WaterlooONN2L 2Y5 Canada Department of Physics and Astronomy Institute for Quantum Computing University of Waterloo ONN2L 2Y5 Canada

We propose a class of metrological resource states whose quantum Fisher information scales optimally in both system size and noise rate. In these states, qubits are partitioned into sensing groups with relatively large correlations within a group but small correlations between groups. The states are obtainable from local Hamiltonian evolution, and we design a metrologically optimal and efficient measurement protocol utilizing time-reversed dynamics and single-qubit local measurements. Using quantum domino dynamics, we also present a protocol free of the time-reversal step that has an estimation error roughly twice the best possible value. Copyright © 2024, The Authors. All rights reserved.

关键词： Qubits

quantum Speedup and Limitations on Matroid Property Problems

学校读者我要写书评

暂无评论

arXiv 2021年

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

This paper initiates the study of quantum algorithms for matroid property problems. It is shown that quadratic quantum speedup is possible for the calculation problem of finding the girth or the number of circuits (bases, flats, hyperplanes) of a matroid, and for the decision problem of deciding whether a matroid is uniform or Eulerian, by giving a uniform lower bound Ω(q( ⌊n/n2⌋ )) on the query complexity for all these problems. On the other hand, for the uniform matroid decision problem, an asymptotically optimal quantum algorithm is proposed which achieves the lower bound, and for the girth problem, an almost optimal quantum algorithm is given with query complexity O(log n q( ⌊n/n2⌋ )). In addition, for the paving matroid decision problem, a lower bound Ω(q( ⌊n/n2⌋ )/n) on the query complexity is obtained, and an O(q( ⌊n/n2⌋ )) quantum algorithm is presented. © 2021, CC BY.

关键词： quantum computers

Opacity of Parametric Discrete Event Systems: Models, Decidability, and Algorithms

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Deng, Weilin Qiu, Daowen Yang, Jingkai The School of Internet Finance and Information Engineering Guangdong University of Finance Guangzhou510521 China The Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-Sen University Guangzhou510006 China The School of Mathematics and Statistics Yulin Normal University Yulin537000 China

Finite automata (FAs) model is a popular tool to characterize discrete event systems (DESs) due to its succinctness. However, for some complex systems, it is difficult to describe the necessary details by means of FAs model. In this paper, we consider a kind of extended finite automata (EFAs) in which each transition carries a predicate over state and event parameters. We also consider a type of simplified EFAs, called Event-Parameters EFAs (EP-EFAs), where the state parameters are removed. Based upon these two parametric models, we investigate the problem of opacity analysis for parametric DESs. First of all, it is shown that EFAs model is more expressive than EP-EFAs model. Secondly, it is proved that the opacity properties for EFAs are undecidable in general. Moreover, the decidable opacity properties for EP-EFAs are investigated. We present the verification algorithms for current-state opacity, initial-state opacity and infinite-step opacity, and then discuss the complexity. This paper establishes a preliminary theory for the opacity of parametric DESs, which lays a foundation for the opacity analysis of complex systems. Copyright © 2023, The Authors. All rights reserved.

关键词： Finite automata

Opacity of Parametric Discrete Event Systems: Models, Decidability, and Algorithms

学校读者我要写书评

暂无评论

TechRxiv

TechRxiv 2023年

作者： Deng, Weilin Qiu, Daowen Yang, Jingkai School of Internet Finance and Information Engineering Guangdong University of Finance Guangzhou510521 China Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-Sen University Guangzhou510006 China School of Mathematics and Statistics Yulin Normal University Yulin537000 China

关键词： Opacity

QHDOPT: A Software for Nonlinear Optimization with quantum Hamiltonian Descent

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kushnir, Samuel Leng, Jiaqi Peng, Yuxiang Fan, Lei Wu, Xiaodi Department of Computer Science University of Maryland United States Department of Mathematics University of Maryland United States Joint Center for Quantum Information and Computer Science University of Maryland United States Department of Mathematics Simons Institute for the Theory of Computing University of California Berkeley United States Department of Engineering Technology University of Houston United States Department of Electrical and Computer Engineering University of Houston United States

We develop an open-source, end-to-end software (named QHDOPT), which can solve nonlinear optimization problems using the quantum Hamiltonian descent (QHD) algorithm. QHDOPT offers an accessible interface and automatically maps tasks to various supported quantum backends (i.e., quantum hardware machines). These features enable users, even those without prior knowledge or experience in quantum computing, to utilize the power of existing quantum devices for nonlinear and nonconvex optimization tasks. In its intermediate compilation layer, QHDOPT employs SimuQ, an efficient interface for Hamiltonian-oriented programming, to facilitate multiple algorithmic specifications and ensure compatible cross-hardware deployment. The detailed documentation of QHDOPT is available at https://***/jiaqileng/QHDOPT. Copyright © 2024, The Authors. All rights reserved.

关键词： quantum computers

Supervisory Control of quantum Discrete Event Systems

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Qiu, Daowen Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China

Discrete event systems (DES) have been deeply developed and applied in practice, but state complexity in DES still is an important problem to be better solved with innovative methods. With the development of quantum computing and quantum control, a natural problem is to simulate DES by means of quantum computing models and to establish quantum DES (QDES). The motivation is twofold: on the one hand, QDES have potential applications when DES are simulated and processed by quantum computers, where quantum systems are employed to simulate the evolution of states driven by discrete events, and on the other hand, QDES may have essential advantages over DES concerning state complexity for imitating some practical problems. So, the goal of this paper is to establish a basic framework of QDES by using quantum finite automata (QFA) as the modelling formalisms, and the supervisory control theorems of QDES are established and proved. Then we present a polynomial-time algorithm to decide whether or not the controllability condition holds. In particular, we construct a number of new examples of QFA to illustrate the supervisory control of QDES and to verify the essential advantages of QDES over classical DES in state complexity. Copyright © 2021, The Authors. All rights reserved.

关键词： Discrete event simulation

Learning quantum Finite Automata with Queries

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Qiu, Daowen Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China

Learning finite automata (termed as model learning) has become an important field in machine learning and has been useful realistic applications. quantum finite automata (QFA) are simple models of quantum computers with finite memory. Due to their simplicity, QFA have well physical realizability, but one-way QFA still have essential advantages over classical finite automata with regard to state complexity (two-way QFA are more powerful than classical finite automata in computation ability as well). As a different problem in quantum learning theory and quantum machine learning, in this paper, our purpose is to initiate the study of learning QFA with queries (naturally it may be termed as quantum model learning), and the main results are regarding learning two basic one-way QFA (1QFA): (1) We propose a learning algorithm for measure-once 1QFA (MO-1QFA) with query complexity of polynomial time;(2) We propose a learning algorithm for measure-many 1QFA (MM-1QFA) with query complexity of polynomial-time, as well. Copyright © 2021, The Authors. All rights reserved.

关键词： Finite automata

State complexity of one-way quantum finite automata together with classical states

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Xiao, Ligang Qiu, Daowen Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China

One-way quantum finite automata together with classical states (1QFAC) proposed in [Journal of computer and System Sciences 81 (2) (2015) 359–375] is a new one-way quantum finite automata (1QFA) model that integrates quantum finite automata (QFA) and deterministic finite automata (DFA). This model uses classical states to control the evolution and measurement of quantum states. As a quantum-classical hybrid model, 1QFAC recognize all regular languages. It was shown that the state complexity of 1QFAC for some languages is essentially superior to that of DFA and other 1QFA. However, the relationships and balances between quantum states and classical states are still not clear in 1QFAC, for example, how to reduce a quantum state by adding classical states, and vice versa. In this paper, our goal is to clarify state complexity problems for 1QFAC. We obtain the following results: (1) We optimize the bound given by Qiu et al. that characterizes the relationship between quantum basis state number and classical state number of 1QFAC as well as the state number of its corresponding minimal DFA for recognizing any given regular language. (2) We give an upper bound showing that how many classical states are needed if the quantum basis states of 1QFAC are reduced without changing its recognition ability. (3) We give a lower bound of the classical state number of 1QFAC for recognizing any given regular language, and the lower bound is exact if the given language is finite. (4) We show that 1QFAC are exponentially more succinct than DFA and probabilistic finite automata (PFA) for recognizing some regular languages that can not be recognized by measure-once 1QFA (MO-1QFA), measure-many 1QFA (MM-1QFA) or multi-letter 1QFA. (5) We reveal essential relationships between 1QFAC, MO-1QFA and multi-letter 1QFA, and induce a result regarding a quantitative relationship between the state number of multi-letter 1QFA and DFA. Copyright © 2021, The Authors. All rights reserved.

关键词： Finite automata