Practical Implementation of a Quantum Backtracking Algorithm

DOI10.1007/978-3-030-38919-2_49MaRDI QIDQ3297790zbMATH OpenOpenAlexFDO

Authors Simon Martiel, Maxime Remaud

Publication date 20 July 2020

Published in SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.11291

zbMATH Keywords

backtracking algorithmCSPgraph coloringquantum walkSAT

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In previous work, Montanaro presented a method to obtain quantum speedups for backtracking algorithms, a general meta-algorithm to solve constraint satisfaction problems (CSPs). In this work, we derive a space efficient implementation of this method. Assume that we want to solve a CSP with $m$ constraints on $n$ variables and that the union of the domains in which these variables take their value is of cardinality $d$. Then, we show that the implementation of Montanaro's backtracking algorithm can be done by using $O(nlogd)$ data qubits. We detail an implementation of the predicate associated to the CSP with an additional register of $O(logm)$ qubits. We explicit our implementation for graph coloring and SAT problems, and present simulation results. Finally, we discuss the impact of the usage of static and dynamic variable ordering heuristics in the quantum setting.

Recommendations

• Quantum-walk speedup of backtracking algorithms
• Quantum algorithms revisited
• QCL implementation of quantum search algorithms
• scientific article; zbMATH DE number 1839431
• Quantum Algorithms
• Quantum algorithms
• An algorithm for optimizing quantum reversible logic synthesis
• Implementation of efficient quantum search algorithms on NISQ computers
• Implementing a deterministic search algorithm with a single qubit
• Implementation of quantum algorithms with resonant interactions

Cites work

• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• A survey on vertex coloring problems
• Exponential algorithmic speedup by a quantum walk
• scientific article; zbMATH DE number 6118223 (Why is no real title available?)
• scientific article; zbMATH DE number 5485493 (Why is no real title available?)
• Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
• Quantum lattice enumeration and tweaking discrete pruning
• Quantum Walk Algorithm for Element Distinctness
• Quantum Walk Based Search Algorithms
• QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
• Quantum-walk speedup of backtracking algorithms
• Theory and Applications of Satisfiability Testing
• Time-efficient quantum walks for 3-distinctness

Cited in

(5)

• Quantum-walk speedup of backtracking algorithms
• scientific article; zbMATH DE number 1929929 (Why is no real title available?)
• scientific article; zbMATH DE number 7496272 (Why is no real title available?)
• Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
• Concrete analysis of quantum lattice enumeration

Describes a project that uses

Uses Software

• MiniSat

This page was built for publication: Practical Implementation of a Quantum Backtracking Algorithm

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