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

Discrete-Query quantum Algorithm for NAND Trees

学校读者我要写书评

暂无评论

Theory of computing 2009年 5卷 119-123页

作者： Childs, Andrew M. Cleve, Richard Jordan, Stephen P. Yonge-Mallo, David Department of Combinatorics & Optimization and Institute for Quantum Computing University of Waterloo Canada David R. Cheriton School of Computer Science and Institute for Quantum Computing University of Waterloo and Perimeter Institute for Theoretical Physics Canada Institute for Quantum Information California Institute of Technology United States David R. Cheriton School of Computer Science and Institute for Quantum Computing University of Waterloo Canada

This is a comment on the article "A quantum Algorithm for the Hamiltonian NAND Tree" by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, Theory of computing 4 (2008) 169–190. That paper gave a quantum algorithm for evaluating NAND trees with running time O(√N) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using N1/2+o(1) queries in the conventional (discrete) quantum query model. © 2009 Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo.

关键词：

The platypus of the quantum channel zoo

学校读者我要写书评

暂无评论

The platypus of the quantum channel zoo

IEEE International Symposium on Information Theory

作者： Felix Leditzky Debbie Leung Vikesh Siddhu Graeme Smith John A. Smolin Department of Mathematics &amp IQUIST University of Illinois at Urbana-Champaign Institute for Quantum Computing &amp Department of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics JILA University of Colorado Boulder Department of Physics &amp Quantum Computing Group Carnegie Mellon University CTQM &amp Department of Physics University of Colorado Boulder IBM Quantum

ISBN: (数字)9781665421591

ISBN: (纸本)9781665421607

A key objective of quantum information theory is to understand quantum channels and their capacities. Here we study a remarkably simple, low-dimensional, single-parameter family of quantum channels with exotic quantum information-theoretic features. We focus on the simplest example from this family, a qutrit-to-qutrit channel intuitively obtained by hybridizing together a simple degradable channel with a completely useless qubit channel. Such hybridizing makes this channel’s capacities behave in a variety of interesting ways. For instance, the private and classical capacity of this channel coincide and can be explicitly calculated, even though the channel lies outside any previous class with calculable capacities. Moreover, the quantum capacity of the channel can be computed explicitly, given a clear and compelling conjecture is true. This "spin alignment conjecture", which may be of independent interest, is proved in certain special cases and backed numerically in certain other cases. Finally, we generalize the qutrit channel; the resulting channels and their capacities display similarly rich behavior. Our companion paper [22] demonstrates superadditivity when transmitting quantum information jointly across our qutrit channel used with a variety of assisting channels, in a manner unknown before.

关键词： Channel capacity quantum channels Qubit quantum mechanics Behavioral sciences Information theory

New one shot quantum protocols with application to communication complexity

学校读者我要写书评

暂无评论

New one shot quantum protocols with application to communica...

作者： Anshu, Anurag Jain, Rahul Mukhopadhyay, Priyanka Shayeghi, Ala Yao, Penghui Centre for Quantum Technologies National University of Singapore Singapore117543 Singapore Centre for Quantum Technologies Department of Computer Science National University of Singapore Singapore117543 Singapore MajuLab CNRS-UNS-NUS-NTU International Joint Research Unit UMI 3654 Singapore Singapore Institute for Quantum Computing Combinatorics and Optimization Department University of Waterloo WaterlooONN2L 3G1 Canada Joint Center for Quantum Information and Computer Science University of Maryland College ParkMD20742-2420 United States

In this paper, we present the following quantum compression protocol ' P ' Let ρ ,σ be quantum states, such that mathrm S left ( ρ σ right ) stackrel mathrm def= mathrm Tr (ρ log ρ - ρ log σ ) , the relative entropy between ρ and σ , is finite. Alice gets to know the eigendecomposition of ρ . Bob gets to know the eigendecomposition of σ . Both Alice and Bob know mathrm S left ( ρ σ right ) and an error parameter varepsilon . Alice and Bob use shared entanglement and after communication of mathcal O(( mathrm S left ( ρ σ right )+1) 4 bits from Alice to Bob, Bob ends up with a quantum state tilde ρ , such that mathrm F(ρ , tilde ρ ) geq 1 - 5 varepsilon , where mathrm F(c) represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao where they considered the special case when ρ and σ are classical probability distributions (or commute with each other) and use shared randomness instead of shared entanglement. We use P to obtain an alternate proof of a direct-sum result for entanglement assisted quantum one-way communication complexity for all relations, which was first shown by Jain et al.. We also present a variant of protocol P in which Bob has some side information about the state with Alice. We show that in such a case, the amount of communication can be further reduced, based on the side information that Bob has. Our second result provides a quantum analog of the widely used classical correlated-sampling protocol. For example, Holenstein used the classical correlated-sampling protocol in his proof of a parallel-repetition theorem for two-player one-round games. © 1963-2012 IEEE.

关键词： Probability distributions

LOCC protocols with bounded width per round optimize convex functions

学校读者我要写书评

暂无评论

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 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

Deterministic Algorithms for the Hidden Subgroup Problem

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Nayak, Ashwin Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo 200 University Ave.W. WaterlooONN2L 3G1 Canada

We present deterministic algorithms for theHidden Subgroup Problem. The first algorithm, for abelian groups, achieves the same asymptotic worst-case query complexity as the optimal randomized algorithm, namely O(√n ), where n is the order of the group. The analogous algorithm for non-abelian groups comes within a √log n factor of the optimal randomized query complexity. The best known randomized algorithm for the Hidden Subgroup Problem has expected query complexity that is sensitive to the input, namely O(√n/m ), where m is the order of the hidden subgroup. In the first version of this article [10, Sec. 5], we asked if there is a deterministic algorithm whose query complexity has a similar dependence on the order of the hidden subgroup. Prompted by this question, Ye and Li [14] present deterministic algorithms for abelian groups which solve the problem with O(√n/m ) queries, and find the hidden subgroup with O(√n(logm)/m + logm) queries. Moreover, they exhibit instances which show that in general, the deterministic query complexity of the problem may be o(√n/m ), and that of finding the entire subgroup may also be o(√n/m ) or even ω(√n/m ). We present a different deterministic algorithm for the Hidden Subgroup Problem that also has query complexity O(√n/m ) for abelian groups. The algorithm is arguably simpler. Moreover, it works for non-abelian groups, and has query complexity O(√(n/m) log(n/m) ) for a large class of instances, such as those over supersolvable groups. We build on this to design deterministic algorithms to find the hidden subgroup for all abelian and some non-abelian instances, at the cost of a logm multiplicative factor increase in the query *** Codes 68Q25, 68Q12 (Primary) 20D99 (Secondary) © 2021, CC BY.

关键词： Group theory

quantum complexity of the Kronecker coefficients

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bravyi, Sergey Chowdhury, Anirban Gosset, David Havlíček, Vojtěch Zhu, Guanyu IBM Quantum IBM T.J. Watson Research Center United States Department of Combinatorics and Optimization University of Waterloo Canada Institute for Quantum Computing University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada

Whether or not the Kronecker coefficients of the symmetric group count some set of combinatorial objects is a longstanding open question. In this work we show that a given Kronecker coefficient is proportional to the rank of a projector that can be measured efficiently using a quantum computer. In other words a Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier, where QMA is the quantum analogue of NP. This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of quantum approximate counting problems that captures the complexity of estimating thermal properties of quantum many-body systems. A second consequence is that deciding positivity of Kronecker coefficients is contained in QMA, complementing a recent NP-hardness result of Ikenmeyer, Mulmuley and Walter. We obtain similar results for the related problem of approximating row sums of the character table of the symmetric group. Finally, we discuss an efficient quantum algorithm that approximates normalized Kronecker coefficients to inverse-polynomial additive error. Copyright © 2023, The Authors. All rights reserved.

关键词： Vector spaces

Improved local spectral gap thresholds for lattices of finite size

学校读者我要写书评

暂无评论

Physical Review B 2020年第16期101卷 165104-165104页

作者： Anurag Anshu Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1 and Perimeter Institute for Theoretical Physics Waterloo Ontario Canada N2L 2Y5

Knabe's theorem lower bounds the spectral gap of a one-dimensional frustration-free local Hamiltonian in terms of the local spectral gaps of finite regions. It also provides a local spectral gap threshold for Hamiltonians that are gapless in the thermodynamic limit, showing that the local spectral gap must scale inverse linearly with the length of the region for such systems. Recent works have further improved upon this threshold, tightening it in the one-dimensional case and extending it to higher dimensions. Here, we show a local spectral gap threshold for frustration-free Hamiltonians on a finite-dimensional lattice that is optimal up to a constant factor that depends on the dimension of the lattice. Our proof is based on the detectability lemma framework and uses the notion of a coarse-grained Hamiltonian (introduced in [Anshu et al., Phys. Rev. B 93, 205142]) as a link connecting the (global) spectral gap and the local spectral gap.

关键词： 1-dimensional spin chains Strongly correlated systems Spin lattice models

On the Power of quantum Distributed Proofs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hasegawa, Atsuya Kundu, Srijita Nishimura, Harumichi Graduate School of Information Science and Technology The University of Tokyo Japan Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Canada Graduate School of Informatics Nagoya University Japan

quantum nondeterministic distributed computing was recently introduced as dQMA (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In dQMA protocols, with the help of quantum proofs and local communication, nodes on a network verify a global property of the network. Fraigniaud et al. showed that, when the network size is small, there exists an exponential separation in proof size between distributed classical and quantum verification protocols, for the equality problem, where the verifiers check if all the data owned by a subset of them are identical. In this paper, we further investigate and characterize the power of the dQMA protocols for various decision problems. First, we give a more efficient dQMA protocol for the equality problem with a simpler analysis. This is done by adding a symmetrization step on each node and exploiting properties of the permutation test, which is a generalization of the SWAP test. We also show a quantum advantage for the equality problem on path networks still persists even when the network size is large, by considering "relay points" between extreme nodes. Second, we show that even in a general network, there exist efficient dQMA protocols for the ranking verification problem, the Hamming distance problem, and more problems that derive from efficient quantum one-way communication protocols. Third, in a line network, we construct an efficient dQMA protocol for a problem that has an efficient two-party QMA communication protocol. Finally, we obtain the first lower bounds on the proof and communication cost of dQMA protocols. To prove a lower bound on the equality problem, we show any dQMA protocol with an entangled proof between nodes can be simulated with a dQMA protocol with a separable proof between nodes by using a QMA communication-complete problem introduced by Raz and Shpilka (CCC 2004). Copyright © 2024, The Authors. All rights reserved.

关键词： Hamming distance