Improved quantum query algorithms for triangle detection and associativity testing

DOI10.1007/s00453-015-0084-9zbMath1359.68091OpenAlexW3136188390WikidataQ107209455 ScholiaQ107209455MaRDI QIDQ513275

Frédéric Magniez, Miklos Santha, Troy Lee

Publication date: 3 March 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0084-9

zbMATH Keywords

quantum algorithmsquery complexityassociativity testinglearning graphstriangle testing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (8)

Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Quantum algorithm for triangle finding in sparse graphs ⋮ Quantum algorithm design: techniques and applications ⋮ On the power of non-adaptive learning graphs ⋮ Unnamed Item ⋮ Parameterized aspects of triangle enumeration ⋮ Extended learning graphs for triangle finding ⋮ Unnamed Item

Cites Work

• On the power of non-adaptive learning graphs
• QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Verification of Identities
• Quantum Algorithms for the Triangle Problem
• Span programs for functions with constant-sized 1-certificates
• The Quantum Complexity of Group Testing
• Nested Quantum Walks with Quantum Data Structures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved quantum query algorithms for triangle detection and associativity testing