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

19th International Conference on Formal Power Series and Algebraic combinatorics, FPSAC'07

作者： Mansour, Toufik Severini, Simone Department of Mathematics University of Haifa Haifa 31905 Israel Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Waterloo N2L 3G1 Canada

A grid polygon is a polygon whose vertices are points of a grid. We define an injective map between permutations of length n and a subset of grid polygons on n vertices, which we call consecutive-minima polygons. By the kernel method, we enumerate sets of permutations whose consecutive-minima polygons satisfy specific geometric conditions. We deal with 2-variate and 3-variate generating functions.

关键词： Grid polygons Kernel method Permutations

来源：评论

学校读者我要写书评

暂无评论

The Bose-Hubbard model is QMA-Complete

引用

Theory of computing 2015年 11卷 491-603页

作者： Childs, Andrew M. Gosset, David Webb, Zak Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo Canada Department of Physics and Astronomy and Institute for Quantum Computing University of Waterloo Canada

The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMAcomplete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i. e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients. © 2015 Aleksandrs Belovs and Eric Blais.

关键词： Hamiltonians

来源：评论

学校读者我要写书评

暂无评论

Parallelizing the Weil and Tate pairings

Parallelizing the Weil and Tate pairings

引用

13th IMA International Conference on Cryptography and Coding, IMACC 2011

作者： Aranha, Diego F. Knapp, Edward Menezes, Alfred Rodríguez-Henríquez, Francisco Institute of Computing University of Campinas Brazil Department of Combinatorics and Optimization University of Waterloo Canada CINVESTAV-IPN Computer Science Department Mexico

ISBN: (纸本)9783642255151

In the past year, the speed record for pairing implementations on desktop-class machines has been broken several times. The speed records for asymmetric pairings were set on a single processor. In this paper, we describe our parallel implementation of the optimal ate pairing over Barreto-Naehrig (BN) curves that is about 1.23 times faster using two cores of an Intel Core i5 or Core i7 machine, and 1.45 times faster using 4 cores of the Core i7 than the state-of-the-art implementation on a single core. We instantiate Hess's general Weil pairing construction and introduce a new optimal Weil pairing tailored for parallel execution. Our experimental results suggest that the new Weil pairing is 1.25 times faster than the optimal ate pairing on 8-core extensions of the aforementioned machines. Finally, we combine previous techniques for parallelizing the eta pairing on a supersingular elliptic curve with embedding degree 4, and achieve an estimated 1.24-fold speedup on an 8-core extension of an Intel Core i7 over the previous best technique. © 2011 Springer-Verlag.

关键词： Computers

来源：评论

学校读者我要写书评

暂无评论

Communication Complexity of One-Shot Remote State Preparation

Communication Complexity of One-Shot Remote State Preparatio...

引用

作者： Bab Hadiashar, Shima Nayak, Ashwin Renner, Renato Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo WaterlooN2L 3G1 Canada Institute for Theoretical Physics ETH Zurich Zurich8093 Switzerland

quantum teleportation uses prior shared entanglement and classical communication to send an unknown quantum state from one party to another. Remote state preparation (RSP) is a similar distributed task in which the sender knows the entire classical description of the state to be sent. (This may also be viewed as the task of nonoblivious compression of a single sample from an ensemble of quantum states.) We study the communication complexity of approximate RSP (ARSP) in which the goal is to prepare an approximation of the desired quantum state. Jain (Quant. Inf. Comp., 2006) showed that the worst-case communication complexity of ARSP can be bounded from above in terms of the maximum possible information in an encoding. He also showed that this quantity is a lower bound for communication complexity of (exact) remote state preparation. In this paper, we tightly characterize the worst-case and average-case communication complexity of remote state preparation in terms of nonasymptotic information-theoretic quantities. We also show that the average-case communication complexity of RSP can be much smaller than the worst-case one. In the process, we show that n bits cannot be communicated with less than n transmitted bits in local operations and classical communication protocols. This strengthens a result due to Nayak and Salzman (J. ACM, 2006) and may be of independent interest. © 1963-2012 IEEE.

关键词： Information theory

来源：评论

学校读者我要写书评

暂无评论

quantum search of spatial regions

引用

Theory of computing 2005年 1卷 47-79页

作者： Aaronson, Scott Ambainis, Andris Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada

Can Grover’s algorithm speed up search of a physical region—for example a 2-D grid of size √n × √n? The problem is that √n time seems to be needed for each query, just to move amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time O(√n) for d ≥ 3, or O(√nlog5/2n) for d = 2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fundamental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include almost-tight upper and lower bounds for many search tasks;a generalized algorithm that works for any graph with good expansion properties, not just hypercubes;and relationships among several notions of ‘locality’ for unitary matrices acting on graphs. As an application of our results, we give an O(√n)-qubit communication protocol for the disjointness problem, which improves an upper bound of Høyer and de Wolf and matches a lower bound of Razborov. © 2005 Scott Aaronson and Andris Ambainis.

关键词： Thermodynamics

来源：评论

学校读者我要写书评

暂无评论

Spatial search by continuous-time quantum walks on crystal lattices

引用

Physical Review A 2014年第5期89卷 052337-052337页

作者： Andrew M. Childs Yimin Ge Department of Combinatorics & Optimization and Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada Perimeter Institute for Theoretical Physics Waterloo Ontario Canada

We consider the problem of searching a general d-dimensional lattice of N vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behavior near a Dirac point, we develop algorithms that solve the problem in a time of O(N) for d>2 and O(NlogN) in d=2. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.

关键词： CRYSTAL lattices ALGORITHMS quantum computing quantum computers PROBABILITY theory

来源：评论

学校读者我要写书评

暂无评论

quantum Log-Approximate-Rank Conjecture is also False

arXiv

引用

arXiv 2018年

作者： Anshu, Anurag Boddu, Naresh Goud Touchette, Dave Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics Center for Quantum Technologies National University of Singapore Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics

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. Copyright © 2018, The Authors. All rights reserved.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Lower bound on expected communication cost of quantum Huffman coding 11

Lower bound on expected communication cost of quantum Huffma...

引用

11th Conference on the Theory of quantum Computation, Communication and Cryptography, TQC 2016

作者： Anshu, Anurag Garg, Ankit Harrow, Aram W. Yao, Penghui Centre for Quantum Technologies National University of Singapore Singapore Microsoft Research New England United States Center for Theoretical Physics Massachusetts Institute of Technology United States Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada

ISBN: (纸本)9783959770194

Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of quantum Reverse Shannon theorem. © Anurag Anshu, Ankit Garg, Aram Harrow, and Penghui Yao;licensed under Creative Commons License CC-BY.

关键词： quantum communication

来源：评论

学校读者我要写书评

暂无评论

A characterization of antidegradable qubit channels

arXiv

引用

arXiv 2017年

作者： Paddock, Connor Chen, Jianxin Department of Combinatorics & Optimization University of Waterloo Institute for Quantum Computing University of Waterloo Canada Aliyun Quantum Laboratory

This paper provides a characterization for the set of antidegradable qubit channels. The characterization arises from the correspondence between the antidegradability of a channel and the symmetric extendibility of its Choi operator. Using an inequality derived to describe the set of bipartite qubit states which admit symmetric extension, we are able to characterize the set of all antidegradable qubit channels. Using the characterization we investigate the antidegradability of unital qubit channels and arbitrary qubit channels with respect to the dimension of the environment. We additionally provide a condition which describes qubit channels which are simultaneously degradable and antidegradable along with a classification of self-complementary qubit channels. Copyright © 2017, The Authors. All rights reserved.

关键词： Qubits

来源：评论

学校读者我要写书评

暂无评论

quantum t-designs: t-wise Independence in the quantum World

Quantum t-designs: t-wise Independence in the Quantum World

引用

Annual IEEE Conference on Computational Complexity

作者： Andris Ambainis Joseph Emerson Department of Combinatorics and Optimization and the Institute for Quantum Computing University of Waterloo Canada Department of Applied Mathematics and the Institute for Quantum Computing University of Waterloo Canada

A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t. We then show that an approximate 4-design provides a derandomization of the statedistinction problem considered by Sen (quant-ph/0512085), which is relevant to solving certain instances of the hidden subgroup problem.

关键词： Probability distribution quantum mechanics quantum computing Combinatorial mathematics Mathematical analysis Testing Distributed computing Information theory Measurement units Computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：