Quantum Backtracking in Qrisp Applied to Sudoku Problems
- URL: http://arxiv.org/abs/2402.10060v3
- Date: Wed, 4 Sep 2024 14:59:16 GMT
- Title: Quantum Backtracking in Qrisp Applied to Sudoku Problems
- Authors: Raphael Seidel, René Zander, Matic Petrič, Niklas Steinmann, David Q. Liu, Nikolay Tcholtchev, Manfred Hauswirth,
- Abstract summary: We provide a detailed instruction on implementing the quantum step operator for arbitrary backtracking instances.
For a single controlled diffuser of a binary backtracking tree with depth n, our implementation requires only $6n+14$ CX gates.
This is the first instance of a compilable implementation of this generality, marking a significant and exciting step forward in quantum software engineering.
- Score: 0.52197339162908
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum backtracking algorithm proposed by Ashley Montanaro raised considerable interest, as it provides a quantum speed-up for a large class of classical optimization algorithms. It does not suffer from Barren-Plateaus and transfers well into the fault-tolerant era, as it requires only a limited number of arbitrary angle gates. Despite its potential, the algorithm has seen limited implementation efforts, presumably due to its abstract formulation. In this work, we provide a detailed instruction on implementing the quantum step operator for arbitrary backtracking instances. For a single controlled diffuser of a binary backtracking tree with depth n, our implementation requires only $6n+14$ CX gates. We detail the process of constructing accept and reject oracles for Sudoku problems using our interface to quantum backtracking. The presented code is written using Qrisp, a high-level quantum programming language, making it executable on most current physical backends and simulators. Subsequently, we perform several simulator based experiments and demonstrate solving 4x4 Sudoku instances with up to 9 empty fields. This is, to the best of our knowledge, the first instance of a compilable implementation of this generality, marking a significant and exciting step forward in quantum software engineering.
Related papers
- How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing [0.2184775414778289]
We show that advantages in space complexity are possible for quantum algorithms over their classical counterparts in the streaming model.
We give a simple quantum sketch that encompasses all these results, allowing them to be derived from entirely classical algorithms using our quantum sketch as a black box.
arXiv Detail & Related papers (2024-10-24T17:11:37Z) - Limitations of Noisy Quantum Devices in Computational and Entangling
Power [5.178527492542246]
We show that noisy quantum devices with a circuit depth of more than $O(log n)$ provide no advantages in any quantum algorithms.
We also study the maximal entanglement that noisy quantum devices can produce under one- and two-dimensional qubit connections.
arXiv Detail & Related papers (2023-06-05T12:29:55Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound.
This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
arXiv Detail & Related papers (2023-01-05T11:05:22Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - Quantum communication complexity of linear regression [0.05076419064097732]
We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems.
We propose an efficient quantum protocol for quantum singular value transformation.
arXiv Detail & Related papers (2022-10-04T13:27:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits.
We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
arXiv Detail & Related papers (2022-01-27T13:16:30Z) - Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit.
Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z) - Advanced Equivalence Checking for Quantum Circuits [4.265279817927261]
We propose an advanced methodology for equivalence checking of quantum circuits.
We show that, by exploiting the reversibility of quantum circuits, complexity can be kept feasible.
In contrast to the classical realm, simulation is very powerful in verifying quantum circuits.
arXiv Detail & Related papers (2020-04-17T18:56:23Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.