AN IMPROVED QUANTUM SCHEDULING ALGORITHM

DOI10.1142/S0129054103001984zbMATH Open1075.68029arXivquant-ph/0202033OpenAlexW1981532619MaRDI QIDQ5696934FDOQ5696934

Authors: Lov K. Grover 

Publication date: 19 October 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: The scheduling problem consists of finding a common 1 in two remotely located N bit strings. Denote the number of 1s in the string with the fewer 1s by epsilon*N. Classically, it needs at least O(epsilon*N) bits of communication to find the common 1 (ignoring logarithmic factors). The best known quantum algorithm would require O(sqrt(N)) qubits of communication. This paper gives a modified quantum algorithm to find the common 1 with only O(sqrt(epsilon*N)) qubits of communication.

Full work available at URL: https://arxiv.org/abs/quant-ph/0202033

Recommendations

• An \(R||C_{\max}\) quantum scheduling algorithm
• Computing and Combinatorics
• Quantum communication and complexity.
• Quantum communication based on an algorithm of determining a matrix
• The communication complexity of the Hamming distance problem

zbMATH Keywords

distributed computingquantum computationcommunication complexity

Mathematics Subject Classification ID

Quantum computation (81P68)

Cited In (3)

• Quantum communication based on an algorithm of determining a matrix
• An \(R||C_{\max}\) quantum scheduling algorithm
• Application of quantum approximate optimization algorithm to job shop scheduling problem

This page was built for publication: AN IMPROVED QUANTUM SCHEDULING ALGORITHM

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