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

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

来源：评论

学校读者我要写书评

暂无评论

Robust quantum Walk Search Without Knowing the Number of Marked Vertices

arXiv

引用

arXiv 2021年

作者： Xu, Yongzhen Zhang, Delong Li, Lvzhou Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 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 new 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 (Equation presented). Note that the algorithm need not know the exact number of marked vertices. Consequently, we obtain quantum search algorithms with stronger robustness and practicability. © 2021, CC BY.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

quantum Algorithms for Identifying Hidden Strings with Applications to Matroid Problems

arXiv

引用

arXiv 2022年

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

In this paper, we explore quantum speedups for the problem, inspired by matroid theory, of identifying a pair of n-bit binary strings that are promised to have the same number of 1s and differ in exactly two bits, by using the max inner product oracle and the sub-set oracle. More specifically, given two string s, s0 ∈ {0, 1}n satisfying the above constraints, for any x ∈ {0, 1}n the max inner product oracle Omax(x) returns the max value between s · x and s0 · x, and the sub-set oracle Osub(x) indicates whether the index set of the 1s in x is a subset of that in s or s0. We present a quantum algorithm consuming O(1) queries to the max inner product oracle for identifying the pair {s, s0}, and prove that any classical algorithm requires Ω(n/ log2 n) queries. Also, we present a quantum algorithm consuming n2 + O(√n) queries to the subset oracle, and prove that any classical algorithm requires at least n + Ω(1) queries. Therefore, quantum speedups are revealed in the two oracle models. Furthermore, the above results are applied to the problem in matroid theory of finding all the bases of a 2-bases matroid, where a matroid is called k-bases if it has k bases. © 2022, CC BY.

关键词： quantum theory

来源：评论

学校读者我要写书评

暂无评论

Deterministic quantum search with adjustable parameters: implementations and applications

arXiv

引用

arXiv 2022年

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

Grover’s algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. The original algorithm is probabilistic, returning a marked element with bounded error. There are several schemes to achieve the deterministic version, by using the generalized Grover’s iteration G(α, β):= Sr(β) So(α) composed of phase oracle So(α) and phase rotation Sr(β). However, in all the existing schemes the value range of α and β is limited;for instance, in the three early schemes α and β are determined by the proportion of marked states M/N. In this paper, we break through this limitation by presenting a search framework with adjustable parameters, which allows α or β to be arbitrarily given. The significance of the framework lies not only in the expansion of mathematical form, but also in its application value, as we present two disparate problems which we are able to solve deterministically using the proposed framework, whereas previous schemes are ineffective. © 2022, CC BY.

关键词： Iterative methods

来源：评论

学校读者我要写书评

暂无评论

quantum Algorithm for Online Convex Optimization

arXiv

引用

arXiv 2020年

作者： He, Jianhao Yang, Feidiao Zhang, Jialin Li, Lvzhou Institute of Quantum Computing and Computer Science Theory School of Computer Science and Engineering Sun Yat-Sen University Guangdong Guangzhou China Institute of Computing Technology Chinese Academy of Sciences Beijing China

We explore whether quantum advantages can be found for the zeroth-order online convex optimization problem, which is also known as bandit convex optimization with multi-point feedback. In this setting, given access to zeroth-order oracles (that is, the loss function is accessed as a black box that returns the function value for any queried input), a player attempts to minimize a sequence of adversarially generated convex loss functions. This procedure can be described as a T round iterative game between the player and the adversary. In this paper, we present quantum algorithms for the problem and show for the first time that potential quantum advantages are possible for problems of online convex optimization. Specifically, our contributions are as follows. (i) When the player is allowed to query zeroth-order oracles O(1) times in each round as feedback, we give a quantum algorithm that achieves O(√T) regret without additional dependence of the dimension n, which outperforms the already known optimal classical algorithm only achieving O(√nT) regret. Note that the regret of our quantum algorithm has achieved the lower bound of classical first-order methods. (ii) We show that for strongly convex loss functions, the quantum algorithm can achieve O(log T) regret with O(1) queries as well, which means that the quantum algorithm can achieve the same regret bound as the classical algorithms in the full information setting. Copyright © 2020, The Authors. All rights reserved.

关键词： Convex optimization

来源：评论

学校读者我要写书评

暂无评论

Differentiable quantum computing for Large-scale Linear Control 38

Differentiable Quantum Computing for Large-scale Linear Cont...

引用

38th Conference on Neural Information Processing Systems, NeurIPS 2024

作者： Clayton, Connor Leng, Jiaqi Yang, Gengzhi Qiao, Yi-Ling Lin, Ming C. Wu, Xiaodi Joint Center for Quantum Information and Computer Science University of Maryland United States Department of Computer Science University of Maryland United States Department of Mathematics University of Maryland United States Center for Machine Learning University of Maryland United States Department of Mathematics Simons Institute for the Theory of Computing UC Berkeley United States

As industrial models and designs grow increasingly complex, the demand for optimal control of large-scale dynamical systems has significantly increased. However, traditional methods for optimal control incur significant overhead as problem dimensions grow. In this paper, we introduce an end-to-end quantum algorithm for linear-quadratic control with provable speedups. Our algorithm, based on a policy gradient method, incorporates a novel quantum subroutine for solving the matrix Lyapunov equation. Specifically, we build a quantum-assisted differentiable simulator for efficient gradient estimation that is more accurate and robust than classical methods relying on stochastic approximation. Compared to the classical approaches, our method achieves a super-quadratic speedup. To the best of our knowledge, this is the first end-to-end quantum application to linear control problems with provable quantum advantage. © 2024 Neural information processing systems foundation. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Deterministic Algorithms for the Hidden Subgroup Problem

arXiv

引用

arXiv 2021年

作者： Ye, Zekun Li, Lvzhou Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China Key Laboratory of Machine Intelligence and Advanced Computing Ministry of Education 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 g1, g2 ∈ G, f(g1) = f(g2) iff g1H = g2H for a subgroup H ≤ G, the goal of the decision version is to determine whether H is trivial or not, and the goal of the identification version is to identify H. An algorithm for the problem should query f(g) for g ∈ G at least as possible. Nayak [25] asked whether there exist deterministic algorithms with O(√|G|/|H|) query complexity for HSP. We answer this problem by proving the following results, which also extend the main results of Ref. [30], since here the algorithms do not rely on any prior knowledge of H. (i) When G is a general finite Abelian group, there exist an algorithm with O(√|G|/|H| |) queries to decide the triviality of H and an algorithm to identify H with O(√|G|/|H| log |H| + log |H|) queries. (ii) In general there is no deterministic algorithm for the identification version of HSP with query complexity of O(√|G|/|H|), since there exists an instance of HSP that needs ω(√|G|/|H|) queries to identify H.1 On the other hand, there exist instances of HSP with query complexity far smaller than O(√|G|/|H|), whose query complexity is O(log |G|/|H|) and even O(1). © 2021, CC BY.

关键词： Group theory

来源：评论

学校读者我要写书评

暂无评论

Preparing a commercial quantum key distribution system for certification against implementation loopholes

引用

Physical Review Applied 2024年第4期22卷 044076页

作者： Vadim Makarov Alexey Abrikosov Poompong Chaiwongkhot Aleksey K. Fedorov Anqi Huang Evgeny Kiktenko Mikhail Petrov Anastasiya Ponosova Daria Ruzhitskaya Andrey Tayduganov Daniil Trefilov Konstantin Zaitsev Skolkovo Moscow 121205 Russia Vigo Quantum Communication Center NTI Center for Quantum Communications Department of Physics Faculty of Science Institute for Quantum Computing Department of Physics and Astronomy Quantum technology foundation (Thailand) Bangkok 10110 Thailand QRate Skolkovo Moscow 143026 Russia Institute for Quantum Information & State Key Laboratory of High Performance Computing College of Computer Science and Technology Moscow 119991 Russia atlanTTic Research Center School of Telecommunication Engineering Department of Signal Theory and Communications Moscow 101000 Russia

A commercial quantum key distribution (QKD) system needs to be formally certified to enable its wide deployment. The certification should include the system’s robustness against known implementation loopholes and attacks that exploit them. Here we ready a fiber-optic QKD system for this procedure. The system has a prepare-and-measure scheme with decoy-state BB84 protocol, polarization encoding, a qubit source rate of 312.5 MHz, and is manufactured by QRate. We detail its hardware and postprocessing. We analyze the hardware for known implementation loopholes, search for possible new loopholes, and discuss countermeasures. We then amend the system design to address the highest-risk loopholes identified. We also work out technical requirements on the certification lab and outline its possible structure.

关键词： quantum communication quantum cryptography quantum protocols

来源：评论

学校读者我要写书评

暂无评论

Characterization of exact one-query quantum algorithms

引用

Physical Review A 2020年第2期101卷 022325-022325页

作者： Weijiang Chen Zekun Ye Lvzhou Li Institute of Computer Science Theory School of Data and Computer Science Sun Yat-Sen University Guangzhou 510006 China Center for Quantum Computing Peng Cheng Laboratory Shenzhen 518055 China Ministry of Education Key Laboratory of Machine Intelligence and Advanced Computing Sun Yat-Sen University Guangzhou 510006 China

The quantum query model is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm, and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function f:{0,1}n→{0,1} can be exactly computed by a one-query quantum algorithm if and only if f(x)=xi1 or xi1⊕xi2 (up to isomorphism). Note that, unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of f.

关键词： quantum algorithms

来源：评论

学校读者我要写书评

暂无评论

Polynomial representation of general partial Boolean functions with a single quantum query

arXiv

引用

arXiv 2021年

作者： Guoliang, Xu Daowen, Qiu College of Information Technology Luoyang Normal University Luoyang471934 China Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-Sen University Guangzhou510006 China

Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Until recent years, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Establishing a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one;(2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query;(3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm. Essentially, the first discovery represent a step forward for a fundamental conclusion that the polynomial degree of partial Boolean functions with a single quantum query is one or two, and the last two results contribute a way for searching more nontrival partial Boolean functions that have quantum advantages. Copyright © 2021, The Authors. All rights reserved.

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：