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

Distinguishability-based genuine nonlocality with genuine multipartite entanglement

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Xiong, Zong-Xing Li, Mao-Sheng Zheng, Zhu-Jun Li, Lvzhou Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-Sen University Guangzhou510006 China School of Mathematics South China University of Technology Guangzhou510640 China

A set of orthogonal multipartite quantum states is said to be distinguishability-based genuinely nonlocal (also genuinely nonlocal, for abbreviation) if the states are locally indistinguishable across any bipartition of the subsystems. This form of multipartite nonlocality, although more naturally arising than the recently popular "strong nonlocality" in the context of local distinguishability, receives much less attention. In this work, we study the distinguishability-based genuine nonlocality of a typical type of genuine multipartite entangled states — the d-dimensional GHZ states, featuring systems with local dimension not limited to 2. In the three-partite case, we find the existence of small genuinely nonlocal sets consisting of these states: we show that the cardinality can at least scale down to linear in the local dimension d, with the linear factor l = 1. Specifically, the method we use is semidefinite program and the GHZ states to construct these sets are special ones which we call "GHZ-lattices". This result might arguably suggest a significant gap between the strength of strong nonlocality and the distinguishability-based genuine nonlocality. Moreover, we put forward the notion of (s, n)-threshold distinguishability and utilizing a similar method, we successfully construct (2, 3)-threshold sets consisting of GHZ states in three-partite systems. © 2022, CC BY.

关键词： quantum entanglement

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

Query complexity of generalized Simon’s problem

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Ye, Zekun Huang, Yunqi Li, Lvzhou Wang, Yuyi Institute of Quantum Computing and Computer Science Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China Guangzhou510006 China Disco Group ETH Zurich Switzerland CRRC Zhuzhou Institute

Simon’s problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon’s problem has been recently applied to break symmetric cryptosystems. Generalized Simon’s problem, denoted by GSP(p, n, k), is a natural extension of Simon’s problem: Given a function f: Zpn → X where X is a finite set and the promise that for any x, y ∈ Zpn, f (x) = f (y) iff x − y ∈ S for a subgroup S ≤ Zpn of rank k n−k}) values and any classical nonadaptive deterministic algorithm for GSP(p, n, k) has to query at least Ω (max{k, √k · pn−k}) values. Hence, we clearly show the classical computing model is less powerful than the quantum counterpart, in terms of query complexity for the generalized Simon’s problem. Moreover, we obtain an upper bound O (max{k, √k · pn−k}) on the classical deterministic query complexity of GSP(p, n, k), by devising a subtle classical algorithm based on group theory and the divide-and-conquer approach. Therefore, we have an almost full characterization of the classical deterministic query complexity of the generalized Simon’s problem. © 2019, CC BY.

关键词： quantum computers

Sample complexity of hidden subgroup problem

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Ye, Zekun Li, Lvzhou Institute of Quantum Computing and Computer Science 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

The hidden subgroup problem (HSP) has been attracting much attention in quantum computing, since several well-known quantum algorithms including Shor algorithm can be described in a uniform framework as quantum methods to address different instances of it. One of the central issues about HSP is to characterize its quantum/classical complexity. For example, from the viewpoint of learning theory, sample complexity is a crucial concept. However, while the quantum sample complexity of the problem has been studied, a full characterization of the classical sample complexity of HSP seems to be absent, which will thus be the topic in this paper. HSP over a finite group is defined as follows: For a finite group G and a finite set V , given a function f : G → V and the promise that for any x, y ∈ G, f(x) = f(xy) iff y ∈ H for a subgroup H ∈ H, where H is a set of candidate subgroups of G, the goal is to identify H. Our contributions are as follows: i) For HSP, we show that the number of uniform examples necessary to learn the hidden subgroup with bounded error is at least Ω max (Hmin ∈H loglog |H|| | H G| |Hmin ∈Hr||HG|| loglog |H|| | H G| |)! , and on the other hand, O (Hmax ∈Hn sr(H), q||HG|| sr(H) o) uniform examples are sufficient, where sr(H) = max r(H) and r(H) is the rank of H. H∈H ii) By concretizing the parameters of HSP, we consider a class of restricted Abelian hidden subgroup problem (rAHSP) and obtain the upper and lower bounds for the sample complexity of rAHSP. iii) We continue to discuss a special case of rAHSP, generalized Simon’s problem (GSP), and show that the sample complexity of GSP is Θ (max n k, pk · pn-ko) . Thus we obtain a complete characterization of the sample complexity of GSP. © 2021, CC BY.

关键词： quantum computers

Polynomial-Time Classical Simulation of Noisy Circuits with Naturally Fault-Tolerant Gates

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Nelson, Jon Rajakumar, Joel Hangleiter, Dominik Gullans, Michael J. Joint Center for Quantum Information & Computer Science University of Maryland and NIST United States Department of Computer Science University of Maryland United States Simons Institute for the Theory of Computing University of California at Berkeley United States

We construct a polynomial-time classical algorithm that samples from the output distribution of low-depth noisy Clifford circuits with any product-state inputs and final single-qubit measurements in any basis. This class of circuits includes Clifford-magic circuits and Conjugated-Clifford circuits, which are important candidates for demonstrating quantum advantage using non-universal gates. Additionally, our results generalize a simulation algorithm for IQP circuits [RWL24] to the case of IQP circuits augmented with CNOT gates, which is another class of non-universal circuits that are relevant to current experiments. Importantly, our results do not require randomness assumptions over the circuit families considered (such as anticoncentration properties) and instead hold for every circuit in each class. This allows us to place tight limitations on the robustness of these circuits to noise. In particular, we show that there is no quantum advantage at large depths with realistically noisy Clifford circuits, even with perfect magic state inputs, or IQP circuits with CNOT gates, even with arbitrary diagonal non-Clifford gates. The key insight behind the algorithm is that interspersed noise causes a decay of long-range entanglement, and at depths beyond a critical threshold, the noise builds up to an extent that most correlations can be classically simulated. To prove our results, we merge techniques from percolation theory with tools from Pauli path analysis. © 2024, CC BY.

关键词： Polynomial approximation

Characterization of exact one-query quantum algorithms

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Chen, Weijiang Ye, Zekun Li, Lvzhou Institute of Computer Science Theory School of Data and Computer Science Sun Yat-Sen University Guangzhou510006 China Center for Quantum Computing Peng Cheng Laboratory Shenzhen518055 China Guangzhou510006 China

The quantum query models 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. Copyright © 2019, The Authors. All rights reserved.

关键词： quantum theory

quantum and classical query complexities for generalized Simon’s problem

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Wu, Zhenggang Qiu, Daowen Tan, Jiawei Li, Hao Cai, Guangya Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China The Guangdong Key Laboratory of Information Security Technology Sun Yat-sen University 510006 China

Simon’s problem is an essential example demonstrating the faster speed of quantum computers than classical computers for solving some problems. The optimal separation between exact quantum and classical query complexities for Simon’s problem has been proved by Cai & Qiu. Generalized Simon’s problem can be described as follows. Given a function f : {0, 1}n → {0, 1}m, with the property that there is some unknown hidden subgroup S such that f(x) = f(y) iff x ⊕ y ∈ S, for any x, y ∈ {0, 1}n, where |S| = 2k for some 0 ≤ k ≤ n. The goal is to find S. For the case of k = 1, it is Simon’s problem. In this paper, we propose an exact quantum algorithm with O(n − k) queries and an non-adaptive deterministic classical algorithm with O(k√2n−k) queries for solving the generalized Simon’s problem. Also, we prove that their lower bounds are Ω(n − k) and Ω(√k2n−k), respectively. Therefore, we obtain a tight exact quantum query complexity Θ(n − k) and an almost tight non-adaptive classical deterministic query complexities Ω(√k2n−k) ∼ O(k√2n−k) for this problem. Copyright © 2019, The Authors. All rights reserved.

关键词： quantum theory

Symmetries, Graph Properties, and quantum Speedups

学校读者我要写书评

暂无评论

Symmetries, Graph Properties, and Quantum Speedups

Annual IEEE Symposium on Foundations of computer Science

作者： Shalev Ben-David Andrew M. Childs András Gilyén William Kretschmer Supartha Podder Daochen Wang Cheriton School of Computer Science University of Waterloo Joint Center for Quantum Information and Computer Science University of Maryland Simons Institute for the Theory of Computing University of California Berkeley University of Texas at Austin University of Ottawa University of Maryland

ISBN: (数字)9781728196213

ISBN: (纸本)9781728196220

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs-where graph symmetry is manifested differently-we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).

关键词： Testing Complexity theory Computational modeling quantum algorithm computer science Symmetric matrices Boolean functions

Verifiable blind quantum computation with identity authentication for different types of clients

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Quan, Junyu Li, Qin Li, Lvzhou School of Mathematics and Computational Science Xiangtan University Xiangtan411105 China School of Computer Science Xiangtan University Xiangtan411105 China Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China

quantum computing has considerable advantages in solving some problems over its classical counterpart. Currently various physical systems are developed to construct quantum computers but it is still challenging and the first use of quantum computers may adopt the cloud style. Blind quantum computing (BQC) provides a solution for clients with limited quantum capabilities to delegate their quantum computation to remote quantum servers while keeping input, output, and even algorithm private. In this paper, we propose three multi-party verifiable blind quantum computing (VBQC) protocols with identity authentication to handle clients with varying quantum capabilities in quantum networks, such as those who can just make measurements, prepare single qubits, or perform a few single-qubit gates. They are client-friendly and flexible since the clients can achieve BQC depending on their own quantum devices and resist both insider outsider attacks in quantum networks. Furthermore, all the three proposed protocols are verifiable, namely that the clients can verify the correctness of their calculations. Copyright © 2022, The Authors. All rights reserved.

关键词： Qubits