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

Query Complexity of Unitary Operation Discrimination

学校读者我要写书评

暂无评论

SSRN

SSRN 2022年

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

Discrimination of unitary operations is fundamental in quantum computation and information. A lot of quantum algorithms including the well-known DeutschJozsa algorithm, Simon’s algorithm, and Grover’s algorithm can essentially be regarded as discriminating among individual, or sets of unitary operations (oracle operators). The problem of discriminating between two unitary operations U and V can be described as: Given X ∈ { U,V }, determine which one X is. If X is given with multiple copies, then one can design an adaptive procedure that takes multiple queries to X to output the identification result of X . In this paper, we consider the problem: How many queries are required for achieving a desired failure probability ϵ of discrimination between U and V . We prove in a uniform framework: (i) if U and V are discriminated with bound error ϵ , then the number of queries T must satisfy, and (ii) if they are discriminated with one-sided error ϵ , then there is, where Θ( W ) denotes the length of the smallest arc containing all the eigenvalues of W on the unit circle. © 2022, The Authors. All rights reserved.

关键词： quantum computers

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

Query complexity of unitary operation discrimination

学校读者我要写书评

暂无评论

arXiv 2020年

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

Discrimination of unitary operations is fundamental in quantum computation and information. A lot of quantum algorithms including the well-known Deutsch-Jozsa algorithm, Simon's algorithm, and Grover's algorithm can essentially be regarded as discriminating among individual, or sets of unitary operations (oracle operators). The problem of discriminating between two unitary operations U and V can be described as: Given X ∈ {U, V }, determine which one X is. If X is given with multiple copies, then one can design an adaptive procedure that takes multiple queries to X to output the identification result of X. In this paper, we consider the problem: How many queries are required for achieving a desired failure probability ∊ of discrimination between U and V. We prove in a uniform framework: (i) if U and V are discriminated with bound error ∊, then the number of queries T must satisfy (Equation presented), and (ii) if they are discriminated with one-sided error ∊, then there is (Equation presented), where dke denotes the minimum integer not less than k and Θ(W) denotes the length of the smallest arc containing all the eigenvalues of W on the unit circle. © 2020, CC BY.

关键词： Eigenvalues and eigenfunctions

Optimal Deterministic quantum Algorithm for the Promised Element Distinctness Problem

学校读者我要写书评

暂无评论

SSRN

SSRN 2023年

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

The element distinctness problem is to determine whether a string of $N$ elements, i.e. $x=(x_1,\ldots,x_N)$ where $x_i\in \{1,\ldots,M\}$ and $M\geq N$, contains two elements of the same value (a.k.a colliding pair), for which Ambainis proposed an optimal quantum algorithm. The idea behind Ambainis' algorithm is to first reduce the problem to the promised version in which $x$ is promised to contain at most one colliding pair, and then design an algorithm $\mathcal{A}$ requiring $O(N^{2/3})$ queries based on quantum walk search for the promise problem. However, $\mathcal{A}$ is probabilistic and may fail to give the right answer. We thus, in this work, design a deterministic quantum algorithm for the promise problem which never errs and requires $O(N^{2/3})$ queries. This algorithm is proved optimal. Technically, we modify the quantum walk search operator on quasi-Johnson graph to have arbitrary phases, and then use Jordan's lemma as the analyzing tool to reduce the quantum walk search operator to the generalized Grover's operator. This allows us to utilize the recently proposed fixed-axis-rotation (FXR) method for deterministic quantum search, and hence achieve 100\% success. © 2023, The Authors. All rights reserved.

关键词： quantum computers

Optimal exact quantum algorithm for the promised element distinctness problem

学校读者我要写书评

暂无评论

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

The element distinctness problem is to determine whether a string x = (x1,..., xN) of N elements contains two elements of the same value (a.k.a colliding pair), for which Ambainis proposed an optimal quantum algorithm. The idea behind Ambainis' algorithm is to first reduce the problem to the promised version in which x is promised to contain at most one colliding pair, and then design an algorithm A requiring O(N2/3) queries based on quantum walk search for the promise problem. However, A is probabilistic and may fail to give the right answer. We thus, in this work, design an exact quantum algorithm for the promise problem which never errs and requires O(N2/3) queries. This algorithm is proved optimal. Technically, we modify the quantum walk search operator on quasi-Johnson graph to have arbitrary phases, and then use Jordan's lemma as the analyzing tool to reduce the quantum walk search operator to the generalized Grover's operator. This allows us to utilize the recently proposed fixed-axis-rotation (FXR) method for exact quantum search, and hence achieve 100% success. © 2022, CC BY.

关键词： quantum theory

quantum algorithm for learning secret strings and its experimental demonstration

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Xu, Yongzhen 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 consider the secret-string-learning problem in the teacher-student setting: the teacher has a secret string s ϵ {0, 1}n, and the student wants to learn the secret s by question-answer interactions with the teacher, where at each time, the student can ask the teacher with a pair (x, q) ϵ {0, 1}n× {0, 1, · · · , n-1} and the teacher returns a bit given by the oracle fs(x, q) that indicates whether the length of the longest common prefix of s and x is greater than q or not. Our contributions are as follows. (i) We prove that any classical deterministic algorithm needs at least n queries to the oracle fsto learn the n-bit secret string s in both the worst case and the average case, and also present an optimal classical deterministic algorithm learning any s using n queries. (ii) We obtain a quantum algorithm learning the n-bit secret string s with certainty using ⌈n/2⌉ queries to the oracle fs, thus proving a double speedup over classical counterparts. (iii) Experimental demonstrations of our quantum algorithm on the IBM cloud quantum computer are presented, with average success probabilities of 85:3% and 82:5% for all cases with n = 2 and n = 3 , respectively. © 2022, CC BY.

关键词： Students

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

Characterization, synthesis, and optimization of quantum circuits over multiple-control Z-rotation gates: A systematic study

学校读者我要写书评

暂无评论

arXiv 2023年

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

We conduct a systematic study of quantum circuits composed of multiple-control Z-rotation (MCZR) gates as primitives, since they are widely-used components in quantum algorithms and also have attracted much experimental interest in recent years. Herein, we establish a circuit-polynomial correspondence to characterize the functionality of quantum circuits over the MCZR gate set with continuous parameters. An analytic method for exactly synthesizing such quantum circuit to implement any given diagonal unitary matrix with an optimal gate count is proposed, which also enables the circuit depth optimal for specific cases with pairs of complementary gates. Furthermore, we present a gate-exchange strategy together with a flexible iterative algorithm for effectively optimizing the depth of any MCZR circuit, which can also be applied to quantum circuits over any other commuting gate set. Besides the theoretical analysis, the practical performances of our circuit synthesis and optimization techniques are further evaluated by numerical experiments on two typical examples in quantum computing, including diagonal Hermitian operators and quantum Approximate Optimization Algorithm (QAOA) circuits with tens of qubits, which can demonstrate a reduction in circuit depth by 33.40% and 15.55% on average over relevant prior works, respectively. Therefore, our methods and results provide a pathway for implementing quantum circuits and algorithms on recently developed devices. © 2023, CC BY.

关键词： Iterative methods

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