Quantum complexity of Boolean matrix multiplication and related problems

DOI10.1007/978-3-319-13350-8_13MaRDI QIDQ2944887zbMATH OpenOpenAlexFDO

Authors 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 algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Recommendations

• A time-efficient output-sensitive quantum algorithm for Boolean matrix multiplication
• Improved output-sensitive quantum algorithms for Boolean matrix multiplication
• Quantum Algorithms for the Triangle Problem

Cites work

• A time-efficient output-sensitive quantum algorithm for Boolean matrix multiplication
• Algebraic Methods in Quantum Informatics
• Faster all-pairs shortest paths via circuit complexity
• Finding a Minimum Circuit in a Graph
• scientific article; zbMATH DE number 3573787 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1489998 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• Multiplying matrices faster than coppersmith-winograd
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Powers of tensors and fast matrix multiplication
• Quantum algorithms for matrix products over semirings
• Quantum Algorithms for the Triangle Problem
• Quantum verification of matrix products
• Quantum Walk Algorithm for Element Distinctness
• Regularity lemmas and combinatorial algorithms
• Span programs for functions with constant-sized 1-certificates (extended abstract)
• The quantum query complexity of read-many formulas

Cited in

(7)

• A matrix representation of quantum circuits over non-adjacent qudits
• Quantum algorithms for matrix products over semirings
• scientific article; zbMATH DE number 2051219 (Why is no real title available?)
• A time-efficient output-sensitive quantum algorithm for Boolean matrix multiplication
• Quantum algorithms for matrix products over semirings
• Improved output-sensitive quantum algorithms for Boolean matrix multiplication
• Entropy of operators or why matrix multiplication is hard for depth-two circuits

This page was built for publication: Quantum complexity of Boolean matrix multiplication and related problems

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