Implementing the Grover Algorithm in Homomorphic Encryption Schemes

• URL: http://arxiv.org/abs/2403.04922v1
• Date: Thu, 7 Mar 2024 22:13:14 GMT
• Title: Implementing the Grover Algorithm in Homomorphic Encryption Schemes
• Authors: Pablo Fern\'andez, Miguel A. Martin-Delgado
• Abstract summary: We apply quantum homomorphic encryption schemes suitable for circuits with a decryption number of $T/Tdagger$-gates to Grover's algorithm. The $T/Tdagger$ gate complexity of Grover's algorithm is also analysed in order to show that any Grover circuit can be evaluated homomorphically in an efficient manner.
• Score: 0.25782420501870296
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We apply quantum homomorphic encryption (QHE) schemes suitable for circuits with a polynomial number of $T/T^{\dagger}$-gates to Grover's algorithm, performing a simulation in Qiskit of a Grover circuit that contains 3 qubits. The $T/T^{\dagger}$ gate complexity of Grover's algorithm is also analysed in order to show that any Grover circuit can be evaluated homomorphically in an efficient manner. We discuss how to apply these QHE schemes to allow for the efficient homomorphic evaluation of any Grover circuit composed of $n$ qubits using $n-2$ extra ancilla qubits. We also show how the homomorphic evaluation of the special case where there is only one marked item can be implemented using an algorithm that makes the decryption process more efficient compared to the standard Grover algorithm.

Related papers

• Efficient Implementation of a Quantum Search Algorithm for Arbitrary N [0.0]
  This paper presents an enhancement to Grover's search algorithm for instances where $N$ is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases.
  arXiv  Detail & Related papers  (2024-06-19T19:16:40Z)
• Automatically Identifying Local and Global Circuits with Linear Computation Graphs [45.760716193942685]
  We introduce our circuit discovery pipeline with Sparse Autoencoders (SAEs) and a variant called Transcoders. Our methods do not require linear approximation to compute the causal effect of each node. We analyze three kinds of circuits in GPT-2 Small: bracket, induction, and Indirect Object Identification circuits.
  arXiv  Detail & Related papers  (2024-05-22T17:50:04Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm [0.4511923587827301]
  We find an application of this scheme to quantum homomorphic encryption (QHE) which is an important cryptographic technology useful for delegated quantum computation. We develop QHE schemes with perfect security, $mathcalF$-homomorphism, no interaction between server and client, and quasi-compactness bounded by $O(M)$ where M is the number of gates $T$ in the circuit.
  arXiv  Detail & Related papers  (2023-03-30T14:49:15Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer [2.487445341407889]
  Combination of Depth-First Search and Grover's algorithm to generate Depth-First Grover Search(DFGS) DFGS handles multi-solution searching problems on unstructured databases with an unknown number of solutions. New algorithm attains an average complexity of $mathcalO(msqrtN)$ which performs as efficient as a normal Grover Search.
  arXiv  Detail & Related papers  (2022-10-10T13:10:28Z)
• Quantum multi-programming for Grover's search [6.359294579761927]
  We propose a quantum multi-programming (QMP) algorithm for Grover's search. Our algorithm decomposes Grover's algorithm by the partial diffusion operator and executes the decomposed circuits in parallel by QMP. We prove that this new algorithm increases the rotation angle of the Grover operator which, as a result, increases the success probability.
  arXiv  Detail & Related papers  (2022-07-29T04:05:46Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Quantum statistical mechanics of encryption: reaching the speed limit of classical block ciphers [0.0]
  We cast encryption via classical block ciphers in terms of operator spreading in a dual space of Pauli strings. We quantify the quality of ciphers using measures of delocalization in string space.
  arXiv  Detail & Related papers  (2020-11-12T18:06:27Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.