On finding dense sub-lattices as low energy states of a quantum
Hamiltonian
- URL: http://arxiv.org/abs/2309.16256v1
- Date: Thu, 28 Sep 2023 08:48:38 GMT
- Title: On finding dense sub-lattices as low energy states of a quantum
Hamiltonian
- Authors: J\'ulia Barber\`a Rodr\'iguez, Nicolas Gama, Anand Kumar Narayanan,
David Joseph
- Abstract summary: Lattice-based cryptography is one of the most prominent candidates for post-quantum cryptography.
Shortest Vector Problem (SVP) is to find the shortest non-zero vector in a given lattice.
We study a natural generalization of the SVP known as the $K$-Densest Sub-lattice Problem ($K$-DSP): to find the densest $K$-dimensional sub-lattice of a given lattice.
- Score: 1.3070944530614654
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Lattice-based cryptography has emerged as one of the most prominent
candidates for post-quantum cryptography, projected to be secure against the
imminent threat of large-scale fault-tolerant quantum computers. The Shortest
Vector Problem (SVP) is to find the shortest non-zero vector in a given
lattice. It is fundamental to lattice-based cryptography and believed to be
hard even for quantum computers. We study a natural generalization of the SVP
known as the $K$-Densest Sub-lattice Problem ($K$-DSP): to find the densest
$K$-dimensional sub-lattice of a given lattice. We formulate $K$-DSP as finding
the first excited state of a Z-basis Hamiltonian, making $K$-DSP amenable to
investigation via an array of quantum algorithms, including Grover search,
quantum Gibbs sampling, adiabatic, and Variational Quantum Algorithms. The
complexity of the algorithms depends on the basis through which the input
lattice is presented. We present a classical polynomial-time algorithm that
takes an arbitrary input basis and preprocesses it into inputs suited to
quantum algorithms. With preprocessing, we prove that $O(KN^2)$ qubits suffice
for solving $K$-DSP for $N$ dimensional input lattices. We empirically
demonstrate the performance of a Quantum Approximate Optimization Algorithm
$K$-DSP solver for low dimensions, highlighting the influence of a good
preprocessed input basis. We then discuss the hardness of $K$-DSP in relation
to the SVP, to see if there is reason to build post-quantum cryptography on
$K$-DSP. We devise a quantum algorithm that solves $K$-DSP with run-time
exponent $(5KN\log{N})/2$. Therefore, for fixed $K$, $K$-DSP is no more than
polynomially harder than the SVP.
Related papers
- Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the
Dominating Set Problem [0.0]
Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers.
This paper utilizes novel quantum counters with three good properties to construct the oracle of Grover's algorithm.
arXiv Detail & Related papers (2023-12-14T23:00:35Z) - On sampling determinantal and Pfaffian point processes on a quantum
computer [49.1574468325115]
DPPs were introduced by Macchi as a model in quantum optics the 1970s.
Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one.
Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
arXiv Detail & Related papers (2023-05-25T08:43:11Z) - Distributed exact quantum algorithms for Bernstein-Vazirani and search
problems [9.146620606615889]
We give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases.
We provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods.
arXiv Detail & Related papers (2023-03-19T14:18:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits.
We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
arXiv Detail & Related papers (2022-03-15T09:46:45Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - Lattice sieving via quantum random walks [0.0]
lattice-based cryptography is one of the leading proposals for post-quantum cryptography.
Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of lattice-based cryptography.
We present an algorithm that has a (heuristic) running time of $20.2570 d + o(d)$ where $d$ is the lattice dimension.
arXiv Detail & Related papers (2021-05-12T11:59:30Z) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem.
We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
arXiv Detail & Related papers (2021-03-16T13:57:01Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard.
We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
arXiv Detail & Related papers (2021-02-03T09:20:32Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.