- Learning with Errors is one of the fundamental problems in computational learning theory and has in the last years become the cornerstone of post-quantum cryptography. In this work, we study the quantum sample complexity of Learning with Errors and show that there exists an efficient quantum learning algorithm (with polynomial sample and time complexity) for the Learning with Errors problem where the error distribution is the one used in cryptography. While our quantum learning algorithm does not break the LWE-based encryption schemes proposed in the cryptography literature, it does have some interesting implications for cryptography: first, when building an LWE-based scheme, one needs to be careful about the access to the public-key generation algorithm that is given to the adversary; second, our algorithm shows a possible way for attacking LWE-based encryption by using classical samples to approximate the quantum sample state, since then using our quantum learning algorithm would solve LWE.
- Feb 28 2017 quant-ph physics.chem-ph arXiv:1702.08422v1The concept of correlation is central to all approaches that attempt the description of many-body effects in electronic systems. Multipartite correlation is a quantum information theoretical property that is attributed to quantum states independent of the underlying physics. In quantum chemistry, however, the correlation energy (the energy not seized by the Hartree-Fock ansatz) plays a more prominent role. We show that these two different viewpoints on electron correlation are closely related. The key ingredient turns out to be the energy gap within the symmetry-adapted subspace. We then use a few-site Hubbard model and the stretched H$_2$ to illustrate this connection and to show how the corresponding measures of correlation compare.
- Feb 28 2017 quant-ph arXiv:1702.08335v1The sub-barrier pairs of energy levels of a Hermitian one-dimensional symmetric double well potential are known to merge into one, if the inter-well distance ($a$) is increased slowly. The energy at which the doublets merge are the ground state eigenvalues of independent wells ($\epsilon_0$). We show that if the double well is perturbed mildly by a complex PT-symmetric potential the merging of levels turns into the coalescing of two levels at an exceptional point $a=a_*$. For $a>a_*$, the real part of complex-conjugate eigenvalues coincides with $\epsilon_0$ again. This is an interesting and rare connection between the two phenomena in two domains: Hermiticity and complex PT-symmetry.
- Feb 28 2017 quant-ph arXiv:1702.08427v1
- Feb 28 2017 quant-ph arXiv:1702.08413v1
- Feb 28 2017 quant-ph arXiv:1702.08316v1
- Feb 28 2017 quant-ph arXiv:1702.08269v1
- Feb 28 2017 quant-ph physics.optics arXiv:1702.08228v1
- Feb 28 2017 cond-mat.stat-mech quant-ph arXiv:1702.08227v1
- Feb 28 2017 quant-ph arXiv:1702.08131v1
- Feb 28 2017 quant-ph arXiv:1702.08110v1
- Feb 28 2017 quant-ph cond-mat.supr-con arXiv:1702.08077v1
- Feb 28 2017 quant-ph arXiv:1702.08075v1
- Feb 28 2017 quant-ph arXiv:1702.07996v1
- Feb 28 2017 quant-ph arXiv:1702.07994v1
- Feb 28 2017 quant-ph cond-mat.mes-hall arXiv:1702.07991v1
- Feb 28 2017 quant-ph arXiv:1702.07972v1
- Feb 28 2017 quant-ph arXiv:1702.07967v1
- Feb 28 2017 quant-ph cond-mat.supr-con arXiv:1702.07943v1
- Feb 28 2017 quant-ph cond-mat.mes-hall arXiv:1702.07931v1
- Feb 28 2017 quant-ph arXiv:1702.07926v1
- Feb 28 2017 quant-ph arXiv:1702.07864v1
- Feb 28 2017 quant-ph arXiv:1702.07861v1
- Feb 28 2017 quant-ph arXiv:1702.07846v1
- Feb 28 2017 quant-ph physics.atom-ph arXiv:1702.07785v1
- Feb 28 2017 quant-ph arXiv:1702.07782v1
- Feb 28 2017 quant-ph arXiv:1702.07746v1
- Feb 28 2017 quant-ph physics.optics arXiv:1702.07742v1