Privacy-Preserving Quantum Two-Party Geometric Intersection
- URL: http://arxiv.org/abs/2309.12605v1
- Date: Fri, 22 Sep 2023 03:39:01 GMT
- Title: Privacy-Preserving Quantum Two-Party Geometric Intersection
- Authors: Wen-Jie Liu, Yong Xu, James C. N. Yang, Wen-Bin Yu, and Lian-Hua Chi
- Abstract summary: An efficient privacy-preserving quantum two-party geometric intersection (PQGI) protocol is proposed.
Compared with classical PGI protocols, our proposed protocol not only has higher security, but also holds lower communication complexity.
- Score: 12.902590249089023
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Privacy-preserving computational geometry is the research area on the
intersection of the domains of secure multi-party computation (SMC) and
computational geometry. As an important field, the privacy-preserving geometric
intersection (PGI) problem is when each of the multiple parties has a private
geometric graph and seeks to determine whether their graphs intersect or not
without revealing their private information. In this study, through
representing Alice's (Bob's) private geometric graph G_A (G_B) as the set of
numbered grids S_A (S_B), an efficient privacy-preserving quantum two-party
geometric intersection (PQGI) protocol is proposed. In the protocol, the oracle
operation O_A (O_B) is firstly utilized to encode the private elements of
S_A=(a_0, a_1, ..., a_(M-1)) (S_B=(b_0, b_1, ..., b_(N-1))) into the quantum
states, and then the oracle operation O_f is applied to obtain a new quantum
state which includes the XOR results between each element of S_A and S_B.
Finally, the quantum counting is introduced to get the amount (t) of the states
|a_i+b_j> equaling to |0>, and the intersection result can be obtained by
judging t>0 or not. Compared with classical PGI protocols, our proposed
protocol not only has higher security, but also holds lower communication
complexity.
Related papers
- Full Characterization of the Depth Overhead for Quantum Circuit
Compilation with Arbitrary Qubit Connectivity Constraint [6.799314463590596]
In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits.
In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph.
arXiv Detail & Related papers (2024-02-04T08:29:41Z) - Quantum Privacy-preserving Two-party Circle Intersection Protocol Based
on Phase-encoded Query [4.173390013531535]
Privacy-preserving geometric intersection (PGI) is an important issue in Secure multiparty computation (SMC)
Phase-encoded query method which has been used in some Quantum SMC protocols is suitable to solve the decision problem.
We use the principle of phase-encoded query to solve an important PGI problem, namely privacy-preserving two-party circle intersection.
arXiv Detail & Related papers (2023-09-29T14:49:15Z) - Secure and Efficient Two-party Quantum Scalar Product Protocol With
Application to Privacy-preserving Matrix Multiplication [2.770988618353868]
Two-party quantum scalar product (S2SP) is a promising research area within secure multiparty computation (SMC)
Existing quantum S2SP protocols are not efficient enough, and the complexity is usually close to exponential level.
In this paper, a novel secure two-party quantum scalar product (S2QSP) protocol based on Fourier states is proposed to achieve higher efficiency.
arXiv Detail & Related papers (2023-09-23T14:33:46Z) - 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) - 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) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space.
We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states.
Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
arXiv Detail & Related papers (2022-03-11T17:19:26Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
Coherent control of quantum computations can be used to improve some quantum protocols and algorithms.
We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
arXiv Detail & Related papers (2022-02-10T18:59:52Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical.
In this paper we present a comparative study of two quantum approaches to computing GED.
arXiv Detail & Related papers (2021-11-19T12:35:26Z) - Geometry of Banach spaces: a new route towards Position Based
Cryptography [65.51757376525798]
We study Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games.
The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol.
We show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol.
arXiv Detail & Related papers (2021-03-30T13:55:11Z) - Topological and geometric patterns in optimal bang-bang protocols for
variational quantum algorithms: application to the $XXZ$ model on the square
lattice [0.0]
We find optimal protocols for transformations between the ground states of the square-lattice XXZ model for finite systems sizes.
We identify the minimum time needed for reaching an acceptable error for different system sizes.
We find that protocols within one phase are indeed geometrically correlated.
arXiv Detail & Related papers (2020-12-10T06:45:25Z) - 2D Qubit Placement of Quantum Circuits using LONGPATH [1.6631602844999722]
Two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit.
Our approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.
arXiv Detail & Related papers (2020-07-14T04:09:52Z)
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.