An Improved Claw Finding Algorithm Using Quantum Walk

DOI10.1007/978-3-540-74456-6_48zbMATH Open1147.81302arXiv0708.2584OpenAlexW1601128144MaRDI QIDQ3525599FDOQ3525599

Authors: Seiichiro Tani 

Publication date: 17 September 2008

Published in: Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Abstract: The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. For given two functions, f and g, as an oracle which have domains of size N and M (N<=M), respectively, and the same range, the goal of the problem is to find x and y such that f(x)=g(y). This paper describes an optimal algorithm using quantum walk that solves this problem. Our algorithm can be generalized to find a claw of k functions for any constant integer k>1, where the domains of the functions may have different size.

Full work available at URL: https://arxiv.org/abs/0708.2584

Recommendations

• Claw finding algorithms using quantum walk
• A new quantum claw-finding algorithm for three functions
• Quantum multicollision-finding algorithm
• Quantum algorithm for the multicollision problem
• Computing and Combinatorics

zbMATH Keywords

query complexityquantum computingoracle computation

Mathematics Subject Classification ID

Quantum computation (81P68)

Cited In (9)

• Improved torsion-point attacks on SIDH variants
• Low-gate quantum golden collision finding
• Quantum Walks
• Quantum walk and its application domains: a systematic review
• Quantum key search for ternary LWE
• A new quantum claw-finding algorithm for three functions
• A framework for reducing the overhead of the quantum oracle for use with Grover's algorithm with applications to cryptanalysis of SIKE
• Computing and Combinatorics
• Claw finding algorithms using quantum walk

This page was built for publication: An Improved Claw Finding Algorithm Using Quantum Walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3525599)