Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption

Abstract

As cloud services continue to expand, the security of private data stored and processed in these environments has become paramount. This work delves into quantum homomorphic encryption (QHE), an emerging technology that facilitates secure computation on encrypted quantum data without revealing the underlying information. We reinterpret QHE schemes through classical-quantum circuits, enhancing efficiency and addressing previous limitations related to key computations. Our approach eliminates the need for exponential key preparation by calculating keys in real-time during simulation, leading to a linear complexity in classically controlled gates. We also investigate the $T/T^{†}$-gate complexity associated with various quantum walks, particularly Szegedy quantum and semiclassical algorithms, demonstrating efficient homomorphic implementations across different graph structures. Our simulations, conducted in Qiskit, validate the effectiveness of QHE for both standard and semiclassical walks. The rules for the homomorphic evaluation of the reset and intermediate measurement operations have also been included to perform the QHE of semiclassical walks. Additionally, we introduce the CQC-QHE library, a comprehensive tool that simplifies the construction and simulation of classical-quantum circuits tailored for quantum homomorphic encryption. Future work will focus on optimizing classical functions within this framework and exploring broader graph types to enhance QHE applications in practical scenarios.

RevTex 4.2, 29+7 pages, 19+12 color figures

References in corpus (25)

• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Information and Computation: Classical and Quantum Aspects
• Optimal Encryption of Quantum Bits
• Search via Quantum Walk
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Quantum speedup for active learning agents
• Google in a Quantum Network
• Quantum Google in a Complex Network
• Quantum walks with encrypted data
• Symmetric quantum fully homomorphic encryption with perfect security
• Limitations on information theoretically secure quantum homomorphic encryption
• Quantum fully homomorphic encryption scheme based on universal quantum circuit
• A quantum approach to homomorphic encryption
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Efficient quantum circuits for Szegedy quantum walks
• Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
• Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
• Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
• Discrete-time Semiclassical Szegedy Quantum Walks
• SQUWALS: A Szegedy QUantum WALks Simulator
• Quantum Bayesian Inference with Renormalization for Gravitational Waves
• Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine
• Complex-Phase Extensions of Szegedy Quantum Walk on Graphs