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

3rd Conference on Innovations in Theoretical computer science, ITCS 2012

作者： Ito, Tsuyoshi Kobayashi, Hirotada Watrous, John Institute for Quantum Computing School of Computer Science University of Waterloo Waterloo ON Canada Principles of Informatics Research Division National Institute of Informatics Tokyo Japan

ISBN: (纸本)9781450311151

This paper proves that the computational power of quantum interactive proof systems, with a double-exponentially small gap in acceptance probability between the completeness and soundness cases, is precisely characterized by EXP, the class of problems solvable in exponential time by deterministic Turing machines. This fact, and our proof of it, has implications concerning quantum and classical interactive proof systems in the setting of unbounded error that include the following: • quantum interactive proof systems are strictly more powerful than their classical counterparts in the unbounded-error setting unless PSPACE = EXP, as even unbounded error classical interactive proof systems can be simulated in PSPACE. • The recent proof of Jain, Ji, Upadhyay, and Watrous (STOC 2010) establishing QIP = PSPACE relies heavily on the fact that the quantum interactive proof systems defining the class QIP have bounded error. Our result implies that some nontrivial assumption on the error bounds for quantum interactive proofs is unavoidable to establish this result (unless PSPACE = EXP). • To prove our result, we give a quantum interactive proof system for EXP with perfect completeness and soundness error 1 - 2 -2poly, for which the soundness error bound is provably tight. This establishes another respect in which quantum and classical interactive proof systems differ, because such a bound cannot hold for any classical interactive proof system: distinct acceptance probabilities for classical interactive proof systems must be separated by a gap that is at least (single-)exponentially small. We also study the computational power of a few other related unbounded-error complexity classes. © 2012 ACM.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Trading robustness for correctness and privacy in certain multiparty computations, beyond an honest majority

Trading robustness for correctness and privacy in certain mu...

引用

6th International Conference on Information Theoretic Security, ICITS 2012

作者： Broadbent, Anne Jeffery, Stacey Ranellucci, Samuel Tapp, Alain Institute for Quantum Computing University of Waterloo ON Canada School of Computer Science University of Waterloo ON Canada DIRO Université de Montréal QC Canada

ISBN: (纸本)9783642322839

We improve on the classical results in information-theoreti- cally secure multiparty computation among a set of n participants, by considering the special case of the computation of the addition function over binary inputs in the secure channels model with a simultaneous broadcast channel. This simple function is a useful building block for other applications. The classical results in multiparty computation show that in this model, every function can be computed with information-theoretic security if and only if less than n/2 participants are corrupt. In this article we show that, under certain conditions, this bound can be overcome. More precisely, let t (p), t (r) and t (c) be the privacy, robustness and correctness thresholds;that is, the minimum number of participants that must be actively corrupted in order for privacy, robustness or correctness, respectively, to be compromised. We show a series of novel tradeoffs applicable to the multiparty computation of f(x 1,...,x n ) = x 1 + ... + x n for x i ∈ {0,1}, culminating in the most general tradeoff: t (p) + t (r) = n + 1 and t (c) + t (r) = n + 1. These tradeoffs are applicable as long as t (r)

关键词： Information theory

来源：评论

学校读者我要写书评

暂无评论

Quantifying nonclassicality with local unitary operations

引用

Physical Review A 2012年第4期86卷 042106-042106页

作者： Sevag Gharibian Institute for Quantum Computing and David R. Cheriton School of Computer Science University of Waterloo Waterloo Canada

We propose a measure of nonclassical correlations in bipartite quantum states based on local unitary operations. We prove that the measure is nonzero if and only if the quantum discord is nonzero; this is achieved via a new characterization of zero discord states in terms of the state's correlation matrix. Moreover, our scheme can be extended to ensure that the same relationship holds even with a generalized version of quantum discord in which higher-rank projective measurements are allowed. We next derive a closed-form expression for our scheme in the cases of Werner states and (2×N)-dimensional systems. The latter reveals that for (2×N)-dimensional states, our measure reduces to the geometric discord [Dakić et al., Phys. Rev. Lett. 105, 190502 (2010)]. A connection to the Clauser-Horne-Shimony-Holt inequality is shown. We close with a characterization of all maximally nonclassical, yet separable, (2×N)-dimensional states of rank at most 2 (with respect to our measure).

关键词： UNITARY operators MEASURE theory quantum theory MATHEMATICAL proofs GENERALIZATION DIMENSIONAL analysis

来源：评论

学校读者我要写书评

暂无评论

quantum query complexity of minor-closed graph properties

Quantum query complexity of minor-closed graph properties

引用

作者： Childs, Andrew M. Kothari, Robin Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo Waterloo ON N2L 3G1 Canada David R. Cheriton School of Computer Science and Institute for Quantum Computing University of Waterloo Waterloo ON N2L 3G1 Canada

We study the quantum query complexity of m inor-closed graph properties, which include such problems as determining whether an n-vertex graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties-those that cannot be characterized by a finite set of forbidden subgraphs-have quantum query complexity Θ(n3/2). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n3/2) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems. © 2012 Societ y for Industrial and Applied Mathematics.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Reconstructing strings from substrings with quantum queries

Reconstructing strings from substrings with quantum queries

引用

13th Scandinavian Symposium and Workshops on Algorithm theory, SWAT 2012

作者： Cleve, Richard Iwama, Kazuo Le Gall, François Nishimura, Harumichi Tani, Seiichiro Teruyama, Junichi Yamashita, Shigeru Institute for Quantum Computing School of Computer Science University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada School of Informatics Kyoto University Japan Department of Computer Science University of Tokyo Japan School of Information Science Nagoya University Japan NTT Communication Science Laboratories NTT Corporation Atsugi Japan College of Information Science and Engineering Ritsumeikan University Japan

ISBN: (纸本)9783642311543

This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string S by making queries of the following form: "Is s a substring of S?", where s is a query string over the given alphabet. The number of queries required to identify the string S is the query complexity of this problem. First we show a quantum algorithm that exactly identifies the string S with at most queries, where N is the length of S. This contrasts sharply with the classical query complexity N. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in S, which may have an independent interest. We also prove two lower bounds. The first one is a general lower bound of , which means we cannot achieve a query complexity of O(N 1∈-∈Ε ) for any constant Ε. The other one claims that if we cannot use queries of length roughly between logN and 3 logN, then we cannot achieve a query complexity of any sublinear function in N. © 2012 Springer-Verlag.

关键词： Problem solving

来源：评论

学校读者我要写书评

暂无评论

Correlations in excited states of local Hamiltonians

引用

Physical Review A 2012年第4期85卷 040303(R)-040303(R)页

作者： Jianxin Chen Zhengfeng Ji Zhaohui Wei Bei Zeng Department of Mathematics & Statistics University of Guelph Guelph Ontario Canada Institute for Quantum Computing and School of Computer Science University of Waterloo Waterloo Ontario Canada State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing China Centre for Quantum Technologies National University of Singapore Singapore 117543 Singapore Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada

Physical properties of the ground and excited states of a k-local Hamiltonian are largely determined by the k-particle reduced density matrices (k-RDMs), or simply the k-matrix for fermionic systems—they are at least enough for the calculation of the ground-state and excited-state energies. Moreover, for a nondegenerate ground state of a k-local Hamiltonian, even the state itself is completely determined by its k-RDMs, and therefore contains no genuine >k-particle correlations, as they can be inferred from k-particle correlation functions. It is natural to ask whether a similar result holds for nondegenerate excited states. In fact, for fermionic systems, it has been conjectured that any nondegenerate excited state of a 2-local Hamiltonian is simultaneously a unique ground state of another 2-local Hamiltonian, hence is uniquely determined by its 2-matrix. And a weaker version of this conjecture states that any nondegenerate excited state of a 2-local Hamiltonian is uniquely determined by its 2-matrix among all the pure n-particle states. We construct explicit counterexamples to show that both conjectures are false. We further show that any nondegenerate excited state of a k-local Hamiltonian is a unique ground state of another 2k-local Hamiltonian, hence is uniquely determined by its 2k-RDMs (or 2k-matrix). These results set up a solid framework for the study of excited-state properties of many-body systems.

关键词： Excited states

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for QMA-complete problems

Approximation algorithms for QMA-complete problems

引用

作者： Gharibian, Sevag Kempe, Julia David R. Cheriton School of Computer Science Institute for Quantum Computing University of Waterloo Waterloo N2L 3G1 Canada Blavatnik School of Computer Science Tel Aviv University Tel Aviv 69978 Israel CNRS and LIAFA Université Paris 7 Paris France

Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem (where QMA stands for quantum Merlin Arthur) and initiate its study. We present two main results. The first shows that a nontrivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one) gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora, Karger, and Karpinski [J. Comput. System Sci., 58(1999), p. 193] to the quantum setting and might be of independent interest. © by SIAM. Unauthorized reproduction of this article is prohibited.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel Approximation of Min-max Problems with Applications to Classical and quantum Zero-Sum Games

Parallel Approximation of Min-max Problems with Applications...

引用

Annual IEEE Conference on Computational Complexity

作者： Gus Gutoski Xiaodi Wu Institute for Quantum Computing and School of Computer Science University of Waterloo Waterloo ONT Canada Department of Electrical Engineering and Computer Science University of Michigan Ann Arbor MI USA

This paper presents an efficient parallel algorithm for a new class of min-max problems based on the matrix multiplicative weights update method. Our algorithm can be used to find near-optimal strategies for competitive two-player classical or quantum games in which a referee exchanges any number of messages with one player followed by any number of additional messages with the other. This algorithm considerably extends the class of games which admit parallel solutions, demonstrating for the first time the existence of a parallel algorithm for a game in which one player reacts adaptively to the other. As a consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG(2), SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a new class of semi definite programs whose feasible region consists of lists of semi definite matrices that satisfy a ``transcript-like'' consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP=PSPACE.

关键词： Registers Games Parallel algorithms Bismuth Complexity theory Approximation methods Game theory

来源：评论

学校读者我要写书评

暂无评论

Distributed verification and hardness of distributed approximation

Distributed verification and hardness of distributed approxi...

引用

作者： Sarma, Atish Das Holzer, Stephan Kor, Liah Korman, Amos Nanongkai, Danupon Pandurangan, Gopal Peleg, David Wattenhofer, Roger EBay Research Labs EBay Inc. San Jose CA 95125 United States Computer Distributed Computing Group ETH Zurich CH-8092 Zurich Switzerland Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot 76100 Israel CNRS LIAFA Univ. Paris 7 Paris France Theory and Applications of Algorithms Research Group University of Vienna 1090-Vienna Austria Division of Mathematical Sciences Nanyang Technological University Singapore 637371 Singapore Department of Computer Science Brown University Providence RI 02912 United States

We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has some properties, e.g., if it is a tree or if it is connected (every node knows at the end of the process whether H has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication. In this paper we initiate a systematic study of distributed verification and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and s-t cut verification. We then show applications of these results in deriving strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree (MST), shortest paths, and minimum cut. Many of these results are the first nontrivial lower bounds for both exact and approximate distributed computation, and they resolve previous open questions. Moreover, our unconditional lower bound of approximating MST subsumes and improves upon the previous hardness of approximation bound of Elkin [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456] as well as the lower bound for (exact) MST computation of Peleg and Rubinovich [D. Peleg and V. Rubinovich, SIAM J. Comput., 30 (2000), pp. 1427-1442]. Our result implies that there can be no distributed approximation algorithm for MST that is significantly faster than the current exact algorithm for any approximation factor. Our lower bound proofs show an interesting connection between communication complexity and distributed computing which turns out to be useful in establishing the time complexity of exact and approximate distributed computatio

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

From ground states to local Hamiltonians

引用

Physical Review A 2012年第2期86卷 022339-022339页

作者： Jianxin Chen Zhengfeng Ji Bei Zeng D. L. Zhou Department of Mathematics and Statistics University of Guelph Guelph Ontario Canada Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing China Beijing National Laboratory for Condensed Matter Physics and Institute of Physics Chinese Academy of Sciences Beijing 100190 China

Traditional quantum physics solves ground states for a given Hamiltonian, while quantum information science asks for the existence and construction of certain Hamiltonians for given ground states. In practical situations, one would be mainly interested in local Hamiltonians with certain interaction patterns, such as nearest-neighbor interactions on some types of lattices. A necessary condition for a space V to be the ground-state space of some local Hamiltonian with a given interaction pattern is that the maximally mixed state supported on V is uniquely determined by its reduced density matrices associated with the given pattern, based on the principle of maximum entropy. However, it is unclear whether this condition is in general also sufficient. We examine the situations for the existence of such a local Hamiltonian to have V satisfying the necessary condition mentioned above as its ground-state space by linking to faces of the convex body of the local reduced states. We further discuss some methods for constructing the corresponding local Hamiltonians with given interaction patterns, mainly from physical points of view, including constructions related to perturbation methods, local frustration-free Hamiltonians, as well as thermodynamical ensembles.

关键词： GROUND state (quantum mechanics) HAMILTONIAN operator quantum theory quantum information theory EXISTENCE theorems PERTURBATION (quantum dynamics) MAXIMAL functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：