Quantum Complexity of Boolean Matrix Multiplication and Related Problems

DOI10.1007/978-3-319-13350-8_13zbMath1323.68288OpenAlexW163852484MaRDI QIDQ2944887

François Le Gall

Publication date: 8 September 2015

Published in: Computing with New Resources (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13350-8_13

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improving quantum query complexity of Boolean matrix multiplication using graph collision
• The Quantum Query Complexity of Read-Many Formulas
• Quantum Algorithms for Matrix Products over Semirings
• Powers of tensors and fast matrix multiplication
• Algebraic Methods in Quantum Informatics
• Quantum verification of matrix products
• Finding a Minimum Circuit in a Graph
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication
• Faster all-pairs shortest paths via circuit complexity
• Quantum Algorithms for the Triangle Problem
• Span programs for functions with constant-sized 1-certificates
• Multiplying matrices faster than coppersmith-winograd
• Quantum Walk Algorithm for Element Distinctness

This page was built for publication: Quantum Complexity of Boolean Matrix Multiplication and Related Problems