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

arXiv 2020年

作者： Magniez, Frédéric Nayak, Ashwin IRIF Université de Paris CNRS Paris Cedex 1375205 France Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo 200 University Ave. W. WaterlooONN2L 3G1 Canada

Given x, y ∈ {0, 1}n, Set Disjointness consists in deciding whether xi = yi = 1 for some index i ∈ [n]. We study the problem of computing this function in a distributed computing scenario in which the inputs x and y are given to the processors at the two extremities of a path of length d. Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging O(log n) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from 1/2. We call this problem "Set Disjointness on a Line". Set Disjointness on a Line was introduced by Le Gall and Magniez [LM18] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of O(log n) qubits. In this work, we prove an unconditional lower bound of Ωe(√3 nd2 + √n ) rounds for Set Disjointness on a Line with d + 1 processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of Ωe(3√ nδ2 + √n ) on the number of rounds required for computing the diameter δ of any n-node network with quantum messages of size O(log n) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function f (such as Set Disjointness) has access to the inputs x and y through two separate oracles Ox and Oy, respectively. The restriction is that the algorithm is required to alternately make d queries to Ox and d queries to Oy, with input-independent computation in between queries. The model

关键词： Qubits

来源：评论

学校读者我要写书评

暂无评论

Faster Provable Sieving Algorithms for the Shortest Vector Problem and the Closest Vector Problem on Lattices in p Norm

arXiv

引用

arXiv 2019年

作者： Mukhopadhyay, Priyanka Institute for Quantum Computing University of Waterloo WaterlooON Canada Dept. of Combinatorics and Optimization University of Waterloo WaterlooON Canada

In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in lp norm (1 ≤ p ≤ ∞). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all p norm (1 ≤ p ≤ ∞). The main idea is to divide the space into hypercubes such that each vector can be mapped efficiently to a sub-region. We achieve a time complexity of 22.751n+o(n), which is much less than the 23.849n+o(n) complexity of the previous best algorithm. We also introduce a mixed sieving procedure, where a point is mapped to a hypercube within a ball and then a quadratic sieve is performed within each hypercube. This improves the running time, especially in the 2 norm, where we achieve a time complexity of 22.25n+o(n), while the List Sieve Birthday algorithm has a running time of 22.465n+o(n). We adopt our sieving techniques to approximation algorithms for SVP and CVP in lp norm (1 ≤ p ≤ ∞) and show that our algorithm has a running time of 22.001n+o(n), while previous algorithms have a time complexity of 23.169n+o(n) © 2019, CC BY-NC-ND.

关键词： Geometry

来源：评论

学校读者我要写书评

暂无评论

Fast simulation of planar Clifford circuits

arXiv

引用

arXiv 2020年

作者： Gosset, David Grier, Daniel Kerzner, Alex Schaeffer, Luke Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada Cheriton School of Computer Science University of Waterloo Canada Department of Computer Science and Engineering Department of Mathematics University of California San Diego United States Joint Center for Quantum Information and Computer Science College ParkMD United States

A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be exploited to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime scaling asymptotically as nω/2 1.19 which samples from the output distribution obtained by measuring all n qubits of a planar graph state in given Pauli bases. Here ω is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. Our work improves known classical algorithms with cubic runtime. A key ingredient is a mapping which, given a tree decomposition of some graph G, produces a Clifford circuit with a structure that mirrors the tree decomposition and which emulates measurement of the corresponding graph state. We provide a classical simulation of this circuit with the runtime stated above for planar graphs and otherwise ntω−1 where t is the width of the tree decomposition. Our algorithm incorporates two subroutines which may be of independent interest. The first is a matrix-multiplication-time version of the Gottesman-Knill simulation of multi-qubit measurement on stabilizer states. The second is a new classical algorithm for solving symmetric linear systems over F2 in a planar geometry, extending previous works which only applied to non-singular linear systems in the analogous setting. © 2020, CC BY.

关键词： Timing circuits

来源：评论

学校读者我要写书评

暂无评论

Erasable bit commitment from temporary quantum trust

arXiv

引用

arXiv 2019年

作者： Lütkenhaus, Norbert Marwah, Ashutosh S. Touchette, Dave Institute for Quantum Computing Department of Physics and Astronomy University of Waterloo Perimeter Institute for Theoretical Physics Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Departement d'informatique Institut Quantique Universite de Sherbrooke

We introduce a new setting for two-party cryptography with temporarily trusted third parties. In addition to Alice and Bob in this setting, there are additional third parties, which Alice and Bob both trust to be honest during the protocol. However, once the protocol concludes, there is no guarantee over the behaviour of these third parties. It is possible that they collaborate and act adversarially. Our goal is to use these third parties to facilitate protocols which are impossible in two-party cryptography. We implement a variant of bit commitment in this setting, which we call erasable bit commitment. In this primitive, Alice has the choice of either opening or erasing her commitment after the commit phase. The ability to ask for an erasure allows Alice to ask the trusted parties to erase her commitment in case the trust period is about to expire. This erasure prevents a future coalition of the third parties and Bob from extracting any information about the commitment. However, this ability also makes erasable bit commitment weaker than the standard version of bit commitment. In addition to satisfying the security requirements of bit commitment, our protocol also does not reveal any information about the commitment to the third parties. Lastly, our protocol for this primitive requires a constant number of trusted third parties and can tolerate a small number of corrupt trusted parties as well as implementation errors. Copyright © 2019, The Authors. All rights reserved.

关键词： Cryptography

来源：评论

学校读者我要写书评

暂无评论

Entanglement subvolume law for 2D frustration-free spin systems

arXiv

引用

arXiv 2019年

作者： Anshu, Anurag Arad, Itai Gosset, David Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada Physics Department Technion Israel

Let H be a frustration-free Hamiltonian describing a 2D grid of qudits with local interactions, a unique ground state, and local spectral gap lower bounded by a positive constant. For any bipartition defined by a vertical cut of length L running from top to bottom of the grid, we prove that the corresponding entanglement entropy of the ground state of H is upper bounded by Õ(L5/3). For the special case of a 1D chain, our result provides a new area law which improves upon prior work, in terms of the scaling with qudit dimension and spectral gap. In addition, for any bipartition of the grid into a rectangular region A and its complement, we show that the entanglement entropy is upper bounded as Õ(|∂A|5/3) where ∂A is the boundary of A. This represents the first subvolume bound on entanglement in frustration-free 2D systems. In contrast with previous work, our bounds depend on the local (rather than global) spectral gap of the Hamiltonian. We prove our results using a known method which bounds the entanglement entropy of the ground state in terms of certain properties of an approximate ground state projector (AGSP). To this end, we construct a new AGSP which is based on a robust polynomial approximation of the AND function and we show that it achieves an improved trade-off between approximation error and entanglement. Copyright © 2019, The Authors. All rights reserved.

关键词： Ground state

来源：评论

学校读者我要写书评

暂无评论

quantum Log-Approximate-Rank Conjecture is Also False

Quantum Log-Approximate-Rank Conjecture is Also False

引用

Annual IEEE Symposium on Foundations of Computer Science

作者： Anurag Anshu Naresh Goud Boddu Dave Touchette Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics Waterloo Center for Quantum Technologies National University of Singapore Département d’informatique & Institut Quantique Université de Sherbrooke

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function f, hence refuting the log approximate rank conjecture of Lee and Shraibman [2009]. We provide an alternate proof of their randomized communication complexity lower bound using the information complexity approach. Using the intuition developed there, we derive a polynomially-related quantum communication complexity lower bound using the quantum information complexity approach, thus providing an exponential separation between the log approximate rank and quantum communication complexity of f. Previously, the best known separation between these two measures was (almost) quadratic, due to Anshu, Ben-David, Garg, Jain, Kothari and Lee [CCC, 2017]. This settles one of the main question left open by Chattopadhyay, Mande and Sherif, and refutes the quantum log approximate rank conjecture of Lee and Shraibman [2009]. Along the way, we develop a Shearer-type protocol embedding for product input distributions that might be of independent interest.

关键词： Complexity theory Protocols Random variables quantum communication Measurement quantum mechanics Information theory

来源：评论

学校读者我要写书评

暂无评论

LOCC protocols with bounded width per round optimize convex functions

arXiv

引用

arXiv 2019年

作者： Leung, Debbie W. Winter, Andreas Yu, Nengkun Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo WaterlooON Canada ES-08193 Spain Centre for Quantum Software and Information Faculty of Engineering and Information Technology University of Technology SydneyNSW2007 Australia

We start with the task of discriminating finitely many multipartite quantum states using LOCC protocols, with the goal to optimize the probability of correctly identifying the state. We provide two different methods to show that finitely many measurement outcomes in every step are sufficient for approaching the optimal probability of discrimination. In the first method, each measurement of an optimal LOCC protocol, applied to a dloc-dim local system, is replaced by one with at most 2d2loc outcomes, without changing the probability of success. In the second method, we decompose any LOCC protocol into a convex combination of a number of "slim protocols" in which each measurement applied to a dloc-dim local system has at most d2loc outcomes. To maximize any convex functions in LOCC (including the probability of state discrimination or fidelity of state transformation), an optimal protocol can be replaced by the best slim protocol in the convex decomposition without using shared randomness. For either method, the bound on the number of outcomes per measurement is independent of the global dimension, the number of parties, the depth of the protocol, how deep the measurement is located, and applies to LOCC protocols with infinite rounds, and the "measurement compression" can be done "top-down" - independent of later operations in the LOCC protocol. The second method can be generalized to implement LOCC instruments with finitely many outcomes: if the instrument has n coarse-grained final measurement outcomes, global input dimension D0 and global output dimension Di for i = 1, · · ·, n conditioned on the i-th outcome, then one can obtain the instrument as a convex combination of no more than R = ∑ni=1 D02Di2 − D02 + 1 slim protocols;in other words, log2 R bits of shared randomess suffice. © 2019, CC BY.

关键词： Probability

来源：评论

学校读者我要写书评

暂无评论

quantum insertion-deletion channels

arXiv

引用

arXiv 2019年

作者： Leahy, Janet Touchette, Dave Yao, Penghui University of Calgary Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics State Key Laboratory for Novel Software Technology Nanjing University Nanjing210023 China

We introduce a model of quantum insertion-deletion (insdel) channels. Insdel channels are meant to represent, for example, synchronization errors arising in data transmission. In the classical setting, they represent a strict generalization of the better-understood corruption error channels, and until recently, had mostly resisted effort toward a similar understanding as their corruption counterparts. They have received considerable attention in recent years. Very recently, Haeupler and Shahrasbi developed a framework, using what they call synchronisation strings, that allows one to turn insdel-type errors into corruption-type errors. These can then be handled by the use of standard error-correcting codes. We show that their framework can be extended to the quantum setting, providing a way to turn quantum insdel errors into quantum corruption errors, which can be handled with standard quantum error-correcting codes. Copyright © 2019, The Authors. All rights reserved.

关键词： Crime

来源：评论

学校读者我要写书评

暂无评论

The Projection Games Conjecture and the hardness of approximation of Super-SAT and related problems

arXiv

引用

arXiv 2019年

作者： Mukhopadhyay, Priyanka Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo 200 University Avenue West WaterlooONN2L 3G1 Canada Centre for Quantum Technologies National University of Singapore

The Super-SAT or SSAT problem was introduced by Dinur et al.[1, 2] to prove the NP-hardness of approximation of two popular lattice problems - Shortest Vector Problem(SVP) and Closest Vector Problem(CVP). They conjectured that SSAT is NP-hard to approximate to within a factor of nc (c > 0 is constant), where n is the size of the SSAT instance. In this paper we prove this conjecture assuming the Projection Games Conjecture(PGC), given by Moshkovitz[3]. This implies hardness of approximation of SVP and CVP within polynomial factors, assuming PGC. We also reduce SSAT to the Nearest Codeword Problem(NCP) and Learning Halfspace Problem(LHP), as considered by Arora et al.[4]. This proves that both these problems are NP-hard to approximate within a factor of Nc′/log log n(c′ > 0 is constant) where N is the size of the instances of the respective problems. Assuming PGC these problems are proved to be NP-hard to approximate within polynomial factors. © 2019, CC BY-NC-ND.

关键词： Vectors

来源：评论

学校读者我要写书评

暂无评论

Unified approach to data-driven quantum error mitigation

arXiv

引用

arXiv 2020年

作者： Lowe, Angus Gordon, Max Hunter Czarnik, Piotr Arrasmith, Andrew Coles, Patrick J. Cincio, Lukasz Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo WaterlooONN2L 3G1 Canada Instituto de Física Teórica UAM/CSIC Universidad Autónoma de Madrid Madrid Spain Theoretical Division Los Alamos National Laboratory Los AlamosNM87545 United States Quantum Science Center Oak RidgeTN37931 United States

Achieving near-term quantum advantage will require effective methods for mitigating hardware noise. Data-driven approaches to error mitigation are promising, with popular examples including zero-noise extrapolation (ZNE) and Clifford data regression (CDR). Here we propose a novel, scalable error mitigation method that conceptually unifies ZNE and CDR. Our approach, called variable-noise Clifford data regression (vnCDR), significantly outperforms these individual methods in numerical benchmarks. vnCDR generates training data first via near-Clifford circuits (which are classically simulable) and second by varying the noise levels in these circuits. We employ a noise model obtained from IBM's Ourense quantum computer to benchmark our method. For the problem of estimating the energy of an 8-qubit Ising model system, vnCDR improves the absolute energy error by a factor of 33 over the unmitigated results and by factors 20 and 1.8 over ZNE and CDR, respectively. For the problem of correcting observables from random quantum circuits with 64 qubits, vnCDR improves the error by factors of 2.7 and 1.5 over ZNE and CDR, respectively. Copyright © 2020, The Authors. All rights reserved.

关键词： Errors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：