Improving quantum query complexity of Boolean matrix multiplication using graph collision
From MaRDI portal
Publication:334915
DOI10.1007/s00453-015-9985-xzbMath1353.68096arXiv1112.5855OpenAlexW1964699768MaRDI QIDQ334915
François Le Gall, Frédéric Magniez, Robin Kothari, Stacey Jeffery
Publication date: 1 November 2016
Published in: Algorithmica, Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1112.5855
Related Items
Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Quantum Complexity of Boolean Matrix Multiplication and Related Problems ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improving quantum query complexity of Boolean matrix multiplication using graph collision
- Improved quantum query algorithms for triangle detection and associativity testing
- A fast output-sensitive algorithm for Boolean matrix multiplication
- Matrix multiplication via arithmetic progressions
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- General context-free recognition in less than cubic time
- All pairs shortest distances for graphs with small integer length edges
- Efficient determination of the transitive closure of a directed graph
- The Quantum Query Complexity of Read-Many Formulas
- Quantum verification of matrix products
- Fast recognition of pushdown automaton and context-free languages
- Finding a Minimum Circuit in a Graph
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Strengths and Weaknesses of Quantum Computing
- A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication
- All-Pairs Almost Shortest Paths
- Regularity Lemmas and Combinatorial Algorithms
- Quantum Algorithms for the Triangle Problem
- Span programs for functions with constant-sized 1-certificates
- Multiplying matrices faster than coppersmith-winograd
- Quantum lower bounds by polynomials
- Quantum Query Complexity of Some Graph Problems
- Quantum Query Complexity of State Conversion
This page was built for publication: Improving quantum query complexity of Boolean matrix multiplication using graph collision
