Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm

• URL: http://arxiv.org/abs/2303.17426v2
• Date: Fri, 31 Mar 2023 11:16:32 GMT
• Title: Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm
• Authors: Pablo Fern\'andez, Miguel A. Martin-Delgado
• Abstract summary: 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.
• Score: 0.4511923587827301
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The nonrecursive Bernstein-Vazirani algorithm was the first quantum algorithm to show a superpolynomial improvement over the corresponding best classical algorithm. Here we define a class of circuits that solve a particular case of this problem for second-level recursion. This class of circuits simplifies the number of gates $T$ required to construct the oracle by making it grow linearly with the number of qubits in the problem. We find an application of this scheme to quantum homomorphic encryption (QHE) which is an important cryptographic technology useful for delegated quantum computation. It allows a remote server to perform quantum computations on encrypted quantum data, so that the server cannot know anything about the client's data. Liang developed QHE schemes with perfect security, $\mathcal{F}$-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. Precisely these schemes are suitable for circuits with a polynomial number of gates $T/T^{\dagger}$. Following these schemes, the simplified circuits we have constructed can be evaluated homomorphically in an efficient way.

Related papers

• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  lattice-based cryptography is one of the main candidates of post-quantum cryptography. cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP) Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
  arXiv  Detail & Related papers  (2024-10-17T16:54:41Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• Quantum hashing algorithm implementation [0.0]
  We implement a quantum hashing algorithm which is based on a fingerprinting technique presented by Ambainis and Frievalds, 1988, on gate-based quantum computers. We consider 16-qubit and 27-qubit IBMQ computers with the special graphs of qubits representing nearest neighbor architecture that is not Linear Nearest Neighbor (LNN) one.
  arXiv  Detail & Related papers  (2024-07-14T09:41:16Z)
• Lower $T$-count with faster algorithms [3.129187821625805]
  We contribute to the $T$-count reduction problem by proposing efficient $T$-counts with low execution times. We greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits. We propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated.
  arXiv  Detail & Related papers  (2024-07-11T17:31:20Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
  Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods. We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM) The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• 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)
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings [0.0]
  We propose FABLE, a method to generate approximate quantum circuits for block-encodings of matrices in a fast manner. FABLE circuits have a simple structure and are directly formulated in terms of one- and two-qubit gates. We show that FABLE circuits can be compressed and sparsified.
  arXiv  Detail & Related papers  (2022-04-29T21:06:07Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Quantum Garbled Circuits [9.937090317971313]
  We show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else. Our protocol has the so-called $Sigma$ format with a single-bit challenge, and allows the inputs to be delayed to the last round.
  arXiv  Detail & Related papers  (2020-06-01T17:07:01Z)
• Succinct Blind Quantum Computation Using a Random Oracle [0.8702432681310399]
  We give a new universal blind quantum computation protocol. The protocol's first phase is succinct, that is, its complexity is independent of circuit size.
  arXiv  Detail & Related papers  (2020-04-27T07:47:11Z)

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.