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

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete Algorithms

作者： Amit Chakrabarti Graham Cormode Navin Goyal Justin Thaler Department of Computer Science Dartmouth College University of Warwick Microsoft Research India Simons Institute for the Theory of Computing

ISBN: (纸本)9781611973389

Motivated by the surging popularity of commercial cloud computing services, a number of recent works have studied annotated data streams and variants thereof. In this setting, a computationally weak verifier (cloud user), lacking the resources to store and manipulate his massive input locally, accesses a powerful but untrusted prover (cloud service). The verifier must work within the restrictive data streaming paradigm. The prover, who can annotate the data stream as it is read, must not just supply the final answer but also convince the verifier of its correctness. Ideally, both the amount of annotation from the prover and the space used by the verifier should be sublinear in the relevant input size parameters. A rich theory of such algorithms-which we call Schemes-has started to emerge. Prior work has shown how to leverage the prover’s power to efficiently solve problems that have no non-trivial standard data stream algorithms. However, even though optimal schemes are now known for several basic problems, such optimality holds only for streams whose length is commensurate with the size of the data universe. In contrast, many real-world data sets are relatively sparse, including graphs that contain only o(n~2) edges, and IP traffic streams that contain much fewer than the total number of possible IP addresses, 2~(128) in IPv6. Here we design the first annotation schemes that allow both the annotation and the space usage to be sublinear in the total number of stream updates rather than the size of the data universe. We solve significant problems, including variations of INDEX, SET-DISJOINTNESS, and FREQUENCYMOMENTS, plus several natural problems on graphs. On the other hand, we give a new lower bound that, for the first time, rules out smooth tradeoffs between annotation and space usage for a specific problem. Our technique brings out new nuances in Merlin–Arthur communication complexity-models, and provides a separation between online versions of the MA and AMA mod

关键词： ANNOTATIONS data flow Verifiers use of blank streams PROVER dimensional data rivers Sparse data sublinear

来源：评论

学校读者我要写书评

暂无评论

Control power in perfect controlled teleportation via partially entangled channels

引用

Physical Review A 2014年第5期90卷 052305-052305页

作者： Xi-Han Li Shohini Ghose Department of Physics and Computer Science Wilfrid Laurier University Waterloo Canada Department of Physics Chongqing University Chongqing China Institute for Quantum Computing University of Waterloo Canada

We analyze and evaluate perfect controlled teleportation via three-qubit entangled channels from the point of view of the controller. The key idea in controlled teleportation is that the teleportation is performed only with the participation of the controller. We calculate a quantitative measure of the controller's power and establish a lower bound on the control power required for controlled teleportation. We show that the maximally entangled Greenberger-Horne-Zeilinger state is a suitable channel for controlled teleportation of arbitrary single qubits—the controller's power meets the bound and the teleportation fidelity without the controller's permission is no better than the fidelity of a classical channel. We also construct partially entangled channels that exceed the bound for controlled teleportation of a restricted set of states called the equatorial states. We calculate the minimum entanglement required in these channels to exceed the bound. Moreover, we find that in these restricted controlled teleportation schemes, the partially entangled channels can outperform maximally entangled channels with respect to the controller's power. Our results provide an alternative perspective on controlled teleportation schemes and are of practical interest since we propose useful partially entangled channels.

关键词： Controllers teleportation Fidelity Power control

来源：评论

学校读者我要写书评

暂无评论

quantum Attacks on Classical Proof Systems: The Hardness of quantum Rewinding

Quantum Attacks on Classical Proof Systems: The Hardness of ...

引用

Annual IEEE Symposium on Foundations of computer science

作者： Andris Ambainis Ansis Rosmanis Dominique Unruh University of Latvia and Institute for Advanced Study Princeton Institute for Quantum Computing School of Computer Science University of Waterloo University of Tartu

quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting. More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show that for similar reasons, computationally binding commitments provide almost no security guarantees in a quantum setting. To show these results, we develop the "pick-one trick", a general technique that allows an adversary to find one value satisfying a given predicate, but not two.

关键词： quantum computing Protocols quantum mechanics Cryptography Computational modeling Registers

来源：评论

学校读者我要写书评

暂无评论

A regularity lemma and low-weight approximators for low-degree polynomial threshold functions

引用

theory of computing 2014年 10卷 27-53页

作者： Diakonikolas, Ilias Servedio, Rocco A. Tan, Li-Yang Wan, Andrew School of Informatics University of Edinburgh United Kingdom Department of Computer Science Columbia University United States Simons Institute for the Theory of Computing University of California Berkeley United States

We give a "regularity lemma" for degree-d polynomial threshold functions (PTFs) over the Boolean cube {−1;1}n. Roughly speaking, this result shows that every degree-d PTF can be decomposed into a constant number of subfunctions such that almost all of the subfunctions are close to being regular PTFs. Here a "regular" PTF is a PTF sign(p(x)) where the influence of each variable on the polynomial p(x) is a small fraction of the total influence of p. As an application of this regularity lemma, we prove that for any constants d ≥ 1, Ε > 0, every degree-d PTF over n variables can be approximated to accuracy e by a constant-degree PTF that has integer weights of total magnitude OΕ,d(nd). This weight bound is shown to be optimal up to logarithmic factors. © 2014 Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan.

关键词： Polynomials

来源：评论

学校读者我要写书评

暂无评论

Asymptotically Optimal Topological quantum Compiling

引用

Physical Review Letters 2014年第14期112卷 140504-140504页

作者： Vadym Kliuchnikov Alex Bocharov Krysta M. Svore Institute for Quantum Computing and David R. Cheriton School of Computer Science University of Waterloo Waterloo Ontario N2L 3G1 Canada Quantum Architectures and Computation Group Microsoft Research Redmond Washington 98052 USA

We address the problem of compiling quantum operations into braid representations for non-Abelian quasiparticles described by the Fibonacci anyon model. We classify the single-qubit unitaries that can be represented exactly by Fibonacci anyon braids and use the classification to develop a probabilistically polynomial algorithm that approximates any given single-qubit unitary to a desired precision by an asymptotically depth-optimal braid pattern. We extend our algorithm in two directions: to produce braids that allow only single-strand movement, called weaves, and to produce depth-optimal approximations of two-qubit gates. Our compiled braid patterns have depths that are 20 to 1000 times shorter than those output by prior state-of-the-art methods, for precisions ranging between 10−10 and 10−30.

关键词： ANYONS quantum theory ALGORITHMS PARTICLES (Nuclear physics) PARITY (Physics)

来源：评论

学校读者我要写书评

暂无评论

Symmetric extension of two-qubit states

引用

Physical Review A 2014年第3期90卷 032318-032318页

作者： Jianxin Chen Zhengfeng Ji David Kribs Norbert Lütkenhaus Bei Zeng Department of Mathematics and Statistics University of Guelph Guelph Ontario Canada Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada UTS-AMSS Joint Research Laboratory for Quantum Computation and Quantum Information Processing Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing China State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing China Department of Physics and Astronomy University of Waterloo Waterloo Ontario Canada

A bipartite state ρAB is symmetric extendible if there exists a tripartite state ρABB′ whose AB and AB′ marginal states are both identical to ρAB. Symmetric extendibility of bipartite states is of vital importance in quantum information because of its central role in separability tests, one-way distillation of Einstein-Podolsky-Rosen pairs, one-way distillation of secure keys, quantum marginal problems, and antidegradable quantum channels. We establish a simple analytic characterization for symmetric extendibility of any two-qubit quantum state ρAB; specifically, tr(ρB2)≥tr(ρAB2)−4detρAB. As a special case we solve the bosonic three-representability problem for the two-body reduced density matrix.

关键词： QUBITS quantum states quantum entanglement quantum information science EINSTEIN-Podolsky-Rosen experiment

来源：评论

学校读者我要写书评

暂无评论

Optimal counterfeiting attacks and generalizations for Wiesner's quantum money

引用

7th Conference on theory of quantum Computation, Communication, and Cryptography, TQC 2012

作者： Molina, Abel Vidick, Thomas Watrous, John Institute for Quantum Computing School of Computer Science University of Waterloo Canada Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology United States

ISBN: (纸本)9783642356551

We present an analysis of Wiesner's quantum money scheme, as well as some natural generalizations of it, based on semidefinite programming. For Wiesner's original scheme, it is determined that the optimal probability for a counterfeiter to create two copies of a bank note from one, where both copies pass the bank's test for validity, is (3/4)n for n being the number of qubits used for each note. Generalizations in which other ensembles of states are substituted for the one considered by Wiesner are also discussed, including a scheme recently proposed by Pastawski, Yao, Jiang, Lukin, and Cirac, as well as schemes based on higher dimensional quantum systems. In addition, we introduce a variant of Wiesner's quantum money in which the verification protocol for bank notes involves only classical communication with the bank. We show that the optimal probability with which a counterfeiter can succeed in two independent verification attempts, given access to a single valid n-qubit bank note, is (3/4+ √ 2/8)n. We also analyze extensions of this variant to higher-dimensional schemes. © Springer-Verlag Berlin Heidelberg 2013.

关键词： quantum optics

来源：评论

学校读者我要写书评

暂无评论

Dequantizing read-once quantum formulas 8

Dequantizing read-once quantum formulas

引用

8th Conference on the theory of quantum Computation, Communication and Cryptography, TQC 2013

作者： Cosentino, Alessandro Kothari, Robin Paetznick, Adam David R. Cheriton School of Computer Science Institute for Quantum Computing University of Waterloo Canada

ISBN: (纸本)9783939897552

quantum formulas, defined by Yao [FOCS'93], are the quantum analogs of classical formulas, i.e., classical circuits in which all gates have fanout one. We show that any read-once quantum formula over a gate set that contains all single-qubit gates is equivalent to a read-once classical formula of the same size and depth over an analogous classical gate set. For example, any readonce quantum formula over Toffoli and single-qubit gates is equivalent to a read-once classical formula over Toffoli and not gates. We then show that the equivalence does not hold if the read-once restriction is removed. To show the power of quantum formulas without the read-once restriction, we define a new model of computation called the one-qubit model and show that it can compute all boolean functions. This model may also be of independent interest. © Alessandro Cosentino, Robin Kothari, and Adam Paetznick;.

关键词： Timing circuits

来源：评论

学校读者我要写书评

暂无评论

Positive-partial-transpose-indistinguishable states via semidefinite programming

引用

Physical Review A 2013年第1期87卷 012321-012321页

作者： Alessandro Cosentino []Institute for Quantum Computing and School of Computer Science University of Waterloo Waterloo Ontario Canada

We present a simple semidefinite program whose optimal value is equal to the maximum probability of perfectly distinguishing orthogonal maximally entangled states using any PPT measurement (a measurement whose operators are positive under partial transpose). When the states to be distinguished are given by the tensor product of Bell states, the semidefinite program simplifies to a linear program. In Phys. Rev. Lett. 109, 020506 (2012), Yu, Duan, and Ying exhibit a set of four maximally entangled states in C4⊗C4, which is distinguishable by any PPT measurement only with probability strictly less than 1. Using semidefinite programming, we show a tight bound of 7/8 on this probability (3/4 for the case of unambiguous PPT measurements). We generalize this result by demonstrating a simple construction of a set of k states in Ck⊗Ck with the same property, for any k that is a power of 2. By running numerical experiments, we show the local indistinguishability of certain sets of generalized Bell states in C5⊗C5 and C6⊗C6 previously considered in the literature.

关键词： SEMIDEFINITE programming quantum theory ORTHOGONAL functions NUMERICAL analysis BELL'S theorem

来源：评论

学校读者我要写书评

暂无评论

Development of Lattice QCD Simulation Code Set “Bridge++” on Accelerators

引用

Procedia computer science 2014年 29卷 1701-1710页

作者： S. Motoki S. Aoki T. Aoyama K. Kanaya H. Matsufuru Y. Namekawa H. Nemura Y. Taniguchi S. Ueda N. Ukita Graduate School of Computer Science and Engineering University of Aizu Japan Yukawa Institute for Theoretical Physics Kyoto University Japan Kobayashi-Maskawa Institute for the Origin of Particles and the Universe (KMI) Nagoya University Japan Graduate School of Pure and Applied Sciences University of Tsukuba Japan Computing Research Center High Energy Accelerator Research Organization (KEK) Japan Center for Computational Sciences University of Tsukuba Japan Theory Center IPNS High Energy Accelerator Research Organization (KEK) Japan

We are developing a new code set “Bridge++” for lattice QCD (quantum Chromodynamics) simulations. It aims at an extensible, readable, and portable workbench, while achieving high performance. Bridge++ covers popular lattice actions and numerical algorithms. The code set is constructed in C++ with an object oriented programming. In this paper, we describe our code design focusing on the use of accelerators such as GPGPUs. For portability our implemen- tation employs OpenCL to control the devices while encapsulates the details of manipulation by providing generalized interfaces. The code is successfully applied to several recent accelerators.

关键词： Lattice QCD HPC GPGPU OpenCL

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：