# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 3 Lattices
### Quantum Computers and Lattices  
Lattice problems are thought to be difficult, and there are outstanding questions in this branch of study. Indicative of this fact is the existence and operation of the web page [[https://www.latticechallenge.org/](https://www.latticechallenge.org/)]([https://www.latticechallenge.org/](https://www.latticechallenge.org/)) (accessed on 13 March 2008), which presents sample instances for evaluating algorithms that resolve the shortest vector problem. So, lattices provide one of the most well-known methods for performing post-quantum cryptography, as there are no known algorithms for certain computational lattice problems, and many attempts to devise them have failed. Conversely, lattices have provided us with means of resolving basic issues in quantum computing and cryptography, such as producing a verifiable stream of truly random coins, creating classical protocols that verify that a quantum computer is operating as intended, and creating a quantum money system. In 1994, [PERSON] proposed a polynomial time quantum algorithm for solving the integer factorization and discrete logarithm problems. Current quantum computer technology does not yet allow these problems to be solved with large integers [29]. The quantum routine adopted in [PERSON]'s algorithm, which uses periodicity, does not seem to be suitable for lattice problems. Thus, it leads to the belowconjecture that justifies the significance of lattice-based cryptographic schemes for post-quantum cryptography [30]. There is no polynomial time quantum algorithm that approximates lattice problems within polynomial factors. The development of quantum algorithms has no impact on our comprehension of lattice difficulties, but there are a few highly interesting connections between quantum algorithms and lattice problems, even though genuine quantum algorithms for lattice problems are unknown. The first instance of this purpose was made by [PERSON] in 2004 [31], when [PERSON] showed the connection between lattice problems and quantum computing. In this work, a solution to the unique shortest vector problem was proposed based on the assumption of the existence of an algorithm that solves the hidden subgroup problem in the set-sampling bipartite group. Moreover, the following theorem of [PERSON] was proven, and therefore, a quantum reduction algorithm from \(\Theta(n^{25})\)-unique-SVP to the average case subset sum problem was obtained. If there is a solution to the dihedral coset problem with failure parameter \(f\), then there exists a quantum algorithm that solves the \(\Theta(n^{\frac{1}{2}+2f})\)-unique-SVP. However, quantum algorithms can be helpful to solve certain problems in lattice theory. Suppose there exists an oracle that, given an input of a lattice \(\mathcal{L}\) and a target point \(t\), which is close to the lattice, outputs the closest lattice point to \(t\), and if the point \(t\) is far from the lattice, the output oracle is unspecified. While in a typical model, this appears to be useless, in a quantum environment, it is different. Moreover, in recent years, there have been developments in the theory of lattice field applications of quantum computing. Quantum computing presents the possibility of simulating lattice field theories in parameter regimes, such as the sign-problem-plagued regimes of finite baryon density, topological terms and out-of-equilibrium dynamics, which are essentially inaccessible using the traditional Monte Carlo approach [32]. However, quantum computing can be advantageous even in situations where classical and quantum computations are competitive, such as specific parameter regimes of lattice field theory or, more broadly, reduced energy consumption. More importantly, a modest quantum step translates into a huge classical leap whenever one tackles an exponentially challenging classical problem.