Derandomization of quantum algorithm for triangle finding

DOI10.1016/J.IC.2025.105295MaRDI QIDQ6982306zbMATH OpenFDO

Authors Guanzhong Li, Lvzhou Li

Publication date 19 May 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105295

zbMATH Keywords

quantum algorithmquantum query complexitydiscrete-time quantum walktriangle findingtriangle-sum problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Quantum algorithms and complexity in the theory of computing (68Q12) Signed and weighted graphs (05C22)

Cites work

• scientific article; zbMATH DE number 5320343 (Why is no real title available?)
• scientific article; zbMATH DE number 5485493 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2156272 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• A Fast Monte-Carlo Test for Primality
• Can every randomized algorithm be derandomized?
• Constructing a perfect matching is in random NC
• Derandomization from algebraic hardness: treading the borders
• Derandomization with minimal memory footprint
• Deterministic quantum search with adjustable parameters: implementations and applications
• Extended Learning Graphs for Triangle Finding
• Improved quantum algorithm for triangle finding via combinatorial arguments
• Improved quantum query algorithms for triangle finding and associativity testing
• Nested Quantum Walks with Quantum Data Structures
• Optimal deterministic quantum algorithm for the promised element distinctness problem
• PRIMES is in P
• Pairwise independence and derandomization.
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Probabilistic algorithm for testing primality
• Quantified Derandomization: How to Find Water in the Ocean
• Quantum Algorithms for Element Distinctness
• Quantum Algorithms for the Triangle Problem
• Quantum Walk Algorithm for Element Distinctness
• Query complexity of generalized Simon's problem
• Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem
• Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
• Riemann's hypothesis and tests for primality
• Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
• Span programs for functions with constant-sized 1-certificates (extended abstract)
• The matching problem in general graphs is in quasi-NC
• Undirected connectivity in log-space

This page was built for publication: Derandomization of quantum algorithm for triangle finding

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