An Improved Claw Finding Algorithm Using Quantum Walk

DOI10.1007/978-3-540-74456-6_48MaRDI QIDQ3525599zbMATHOpenAlexFDO

Authors Seiichiro Tani

Publication date 17 September 2008

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

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

zbMATH Keywords

query complexityquantum computingoracle computation

Mathematics Subject Classification ID

Quantum computation (81P68)

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.

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

Cited in

(10)

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

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)