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

Approximation algorithms for quantum many-body problems

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Bravyi, Sergey Gosset, David König, Robert Temme, Kristan IBM T.J. Watson Research Center Yorktown HeightsNY10598 United States Department of Combinatorics & Optimization and Institute for Quantum Computing University of Waterloo WaterlooONN2L 3G1 Canada Institute for Advanced Study & Zentrum Mathematik Technical University of Munich Garching85748 Germany

We discuss classical algorithms for approximating the largest eigenvalue of quantum spin and fermionic Hamiltonians based on semidefinite programming relaxation methods. First, we consider traceless 2-local Hamiltonians H describing a system of n qubits. We give an efficient algorithm that outputs a separable state whose energy is at least λmax/O(log n), where λmax is the maximum eigenvalue of H. We also give a simplified proof of a theorem due to Lieb that establishes the existence of a separable state with energy at least λmax/9. Secondly, we consider a system of n fermionic modes and traceless Hamiltonians composed of quadratic and quartic fermionic operators. We give an efficient algorithm that outputs a fermionic Gaussian state whose energy is at least λmax/O(n log n). Finally, we show that Gaussian states can vastly outperform Slater determinant states commonly used in the Hartree-Fock method. We give a simple family of Hamiltonians for which Gaussian states and Slater determinants approximate λmax within a fraction 1 − O(n−1) and O(n−1) respectively. Copyright © 2018, The Authors. All rights reserved.

关键词： Hamiltonians

Practical quantum appointment scheduling

学校读者我要写书评

暂无评论

Physical Review A 2018年第4期97卷 042320-042320页

作者： Dave Touchette Benjamin Lovitz Norbert Lütkenhaus Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada N2L 3G1 Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1 Perimeter Institute for Theoretical Physics Waterloo Ontario Canada N2L 2Y5 Department of Physics and Astronomy University of Waterloo Waterloo Ontario Canada N2L 3G1

We propose a protocol based on coherent states and linear optics operations for solving the appointment-scheduling problem. Our main protocol leaks strictly less information about each party's input than the optimal classical protocol, even when considering experimental errors. Along with the ability to generate constant-amplitude coherent states over two modes, this protocol requires the ability to transfer these modes back-and-forth between the two parties multiple times with very low losses. The implementation requirements are thus still challenging. Along the way, we develop tools to study quantum information cost of interactive protocols in the finite regime.

关键词： quantum communication quantum information processing with continuous variables quantum optics quantum protocols

The flow of information in interactive quantum protocols : the cost of forgetting

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Laurière, Mathieu Touchette, Dave NYU-ECNU Institute of Mathematical Sciences at Nyu Shanghai Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Perimeter Institute for Theoretical Physics

In the context of two-party interactive quantum communication protocols, we study a recently defined notion of quantum information cost (QIC), which possesses most of the important properties of its classical analogue, see Ref. [Tou15]. Notably, its link with amortized quantum communication complexity has been used in Ref. [BGKK+15] to prove an (almost) tight lower bound on the bounded round quantum complexity of Disjointness. However, the only known characterization of QIC was through a notion of purification of the input state. Although this definition has the advantage to be valid for fully quantum inputs and tasks, its interpretation for classical tasks remained rather obscure. Also, the link between this new notion and other notions of information cost for quantum protocols that had previously appeared in the literature (e.g. in Refs. [JRS03, JN14, KLLGR15]) was not clear, if existent at all. We settle both these issues: For quantum communication with classical inputs, we provide an alternate characterization of QIC in terms of information about the input registers, avoiding any reference to the notion of a purification of the classical input state. We provide an exact operational interpretation of this alternative characterization as the sum of the cost of transmitting information about the classical inputs and the cost of forgetting information about these inputs. To obtain this characterization, we prove a general lemma, the Information Flow Lemma, assessing exactly the transfer of information in general interactive quantum processes. Specializing this lemma to interactive quantum protocols accomplishing classical tasks, we are also able to demystify the link between QIC and these other previous notions of information cost in quantum protocols. Furthermore, we clarify the link between QIC and IC of classical protocols by simulating quantumly classical protocols. Finally, we apply these concepts to argue that any quantum protocol that does not forget informat

关键词： Purification

Estimating the Cost of Generic quantum Pre-image Attacks on SHA-2 and SHA-3 23rd

学校读者我要写书评

暂无评论

Estimating the Cost of Generic Quantum Pre-image Attacks on ...

23rd International Conference on Selected Areas in Cryptography, SAC 2016

作者： Amy, Matthew Di Matteo, Olivia Gheorghiu, Vlad Mosca, Michele Parent, Alex Schanck, John David R. Cheriton School of Computer Science University of Waterloo Waterloo Canada Department of Physics and Astronomy University of Waterloo Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Waterloo Canada Institute for Quantum Computing University of Waterloo Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada Canadian Institute for Advanced Research Toronto Canada

ISBN: (纸本)9783319694528

We investigate the cost of Grover’s quantum search algorithm when used in the context of pre-image attacks on the SHA-2 and SHA-3 families of hash functions. Our cost model assumes that the attack is run on a surface code based fault-tolerant quantum computer. Our estimates rely on a time-area metric that costs the number of logical qubits times the depth of the circuit in units of surface code cycles. As a surface code cycle involves a significant classical processing stage, our cost estimates allow for crude, but direct, comparisons of classical and quantum algorithms. We exhibit a circuit for a pre-image attack on SHA-256 that is approximately 2153.8 surface code cycles deep and requires approximately 2.12.6 logical qubits. This yields an overall cost of 2.166.4 logical-qubit-cycles. Likewise we exhibit a SHA3-256 circuit that is approximately 2.146.5 surface code cycles deep and requires approximately 2.20 logical qubits for a total cost of, again, 2.166.5logical-qubit-cycles. Both attacks require on the order of 2128 queries in a quantum black-box model, hence our results suggest that executing these attacks may be as much as 275 billion times more expensive than one would expect from the simple query analysis. © 2017, Springer International Publishing AG.

关键词： Hash functions

On the circuit diameter of some combinatorial polytopes

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Kafer, Sean Pashkovich, Kanstantsin Sanità, Laura Department of Combinatorics and Optimization University of Waterloo Canada Simons Institute for the Theory of Computing UC Berkeley United States

The combinatorial diameter of a polytope P is the maximum value of a shortest path between two vertices of P, where the path uses the edges of P only. In contrast to the combinatorial diameter, the circuit diameter of P is defined as the maximum value of a shortest path between two vertices of P, where the path uses potential edge directions of P i.e., all edge directions that can arise by translating some of the facets of P. In this paper, we study the circuit diameter of polytopes corresponding to classical combinatorial optimization problems, such as the Matching polytope, the Traveling Salesman polytope and the Fractional Stable Set polytope. Copyright © 2017, The Authors. All rights reserved.

关键词： Timing circuits

Homodyne-detector-blinding attack in continuous-variable quantum key distribution

学校读者我要写书评

暂无评论

Physical Review A 2018年第1期98卷 012312-012312页

作者： Hao Qin Rupesh Kumar Vadim Makarov Romain Alléaume Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada N2L 3G1 Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1 Department of Physics and Astronomy University of Waterloo Waterloo Ontario Canada N2L 3G1 CAS Quantum Network Co. Ltd. 99 Xiupu Road Shanghai 201315 People's Republic of China† Télécom ParisTech LTCI 46 Rue Barrault 75634 Paris Cedex 13 France Department of Physics University of York York YO10 5DD United Kingdom† Russian Quantum Center and MISIS University Moscow Russia

We propose an efficient strategy to attack a continuous-variable (CV) quantum key distribution (QKD) system, which we call homodyne detector blinding. This attack strategy takes advantage of a generic vulnerability of homodyne receivers: A bright light pulse sent on the signal port can lead to a saturation of the detector electronics. While detector saturation has already been proposed to attack CV QKD, the attack we study in this paper has the additional advantage of not requiring an eavesdropper to be phase locked with the homodyne receiver. We show that under certain conditions, an attacker can use a simple laser, incoherent with the homodyne receiver, to generate bright pulses and bias the excess noise to arbitrary small values, fully comprising CV QKD security. These results highlight the feasibility and the impact of the detector-blinding attack. We finally discuss how to design countermeasures in order to protect against this attack.

关键词： quantum cryptography

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields 27

学校读者我要写书评

暂无评论

Efficient quantum algorithms for computing class groups and ...

27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

作者： Biasse, Jean-François Song, Fang Department of Mathematics and Statistics University of South Florida United States Department of Combinatorics Optimization and Institute for Quantum Computing University of Waterloo Canada

ISBN: (纸本)9781510819672

This paper gives polynomial time quantum algorithms for computing the ideal class group (CGP) under the Generalized Riemann Hypothesis and solving the principal ideal problem (PIP) in number fields of arbitrary degree. These are are fundamental problems in number theory and they are connected to many unproven conjectures in both analytic and algebraic number theory. Previously the best known algorithms by Hallgren [20] only allowed to solve these problems in quantum polynomial time for number fields of constant degree. In a recent breakthrough, Eisentrager et al. [11] showed how to compute the unit group in arbitrary fields, thus opening the way to the resolution of CGP and PIP in the general case. For example, Biasse and Song [3] pointed out how to directly apply this result to solve PIP in classes of cyclotomic fields of arbitrary degree. The methods we introduce in this paper run in quantum polynomial time in arbitrary classes of number fields. They can be applied to solve other problems in computational number theory as well including computing the ray class group and solving relative norm equations. They are also useful for ongoing cryptanalysis of cryptographic schemes based on ideal lattices [5, 10]. Our algorithms generalize the quantum algorithm for computing the (ordinary) unit group [11]. We first show that CGP and PIP reduce naturally to the computation of S-unit groups, which is another fundamental problem in number theory. Then we show an efficient quantum reduction from computing 5-units to the continuous hidden subgroup problem introduced in [11]. This step is our main technical contribution, which involves careful analysis of the metrical properties of lattices to prove the correctness of the reduction. In addition, we show how to convert the output into an exact compact representation, which is convenient for further algebraic manipulations.

关键词： Number theory

An efficient post-quantum one-time signature scheme 22nd

学校读者我要写书评

暂无评论

22nd International Conference on Selected Areas in Cryptography, SAC 2015

作者： Kalach, Kassem Safavi-Naini, Reihaneh Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo WaterlooON Canada Department of Computer Science University of Calgary Calgary Canada

ISBN: (纸本)9783319313009

One-time signature (OTS) schemes are important cryptographic primitives that can be constructed using one-way functions, and provide post-quantum security. They have found diverse applications including forward security and broadcast authentication. OTS schemes are time-efficient, but their space complexity is high: the sizes of signatures and keys are linear in the message size. Regular schemes (e.g., based on discrete logarithm or factoring problems, and their variants), however, have very low space complexity but are not time-efficient. Therefore, in particular, they are not suitable for resource-constraint devices. Many widely used signature schemes are not post-quantum. In this paper, we give a signature scheme that has the advantages of the previous two approaches. It provides constant-size short signatures, and is much more time-efficient than schemes in the second approach. We prove that our scheme is post-quantum secure as long as the SVP in ideal lattices is hard in the presence of a quantum computer. We use SWIFFT: a family of provable collision-resistant functions, which have efficient implementations, comparable with that of SHA-256, hence our proposed scheme could be used on resource-constrained devices. © Springer International Publishing Switzerland 2016.

关键词： quantum computers

Homodyne-detector-blinding attack in continuous-variable quantum key distribution

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Qin, Hao Kumar, Rupesh Makarov, Vadim Alleaúme, Romain Institute for Quantum Computing University of Waterloo WaterlooONN2L 3G1 Canada Department of Combinatorics and Optimization University of Waterloo WaterlooONN2L 3G1 Canada Department of Physics and Astronomy University of Waterloo WaterlooONN2L 3G1 Canada Cas Quantum Network Co. Ltd. 99 Xiupu road Shanghai201315 China Department of Physics University of York YorkYO10 5DD United Kingdom Russian Quantum Center and Misis University Moscow Russia Télécom ParisTech Ltci 46 rue Barrault Paris Cedex 1375634 France

We propose an efficient strategy to attack a continuous-variable quantum key distribution (CVQKD) system, that we call homodyne detector blinding. This attack strategy takes advantage of a generic vulnerability of homodyne receivers: A bright light pulse sent on the signal port can lead to a saturation of the detector electronics. While detector saturation has already been proposed to attack CV-QKD, the attack we study in this paper has the additional advantage of not requiring an eavesdropper to be phase locked with the homodyne receiver. We show that under certain conditions, an attacker can use a simple laser, incoherent with the homodyne receiver, to generate bright pulses and bias the excess noise to arbitrary small values, fully comprising CV-QKD security. These results highlight the feasibility and the impact of the detector blinding attack. We finally discuss how to design countermeasures in order to protect against this attack. Copyright © 2018, The Authors. All rights reserved.

关键词： Homodyne detection