Asymptotically Improved Circuit for $d$-ary Grover's Algorithm with Advanced Decomposition of $n$-qudit Toffoli Gate

• URL: http://arxiv.org/abs/2012.04447v3
• Date: Wed, 18 May 2022 14:08:07 GMT
• Title: Asymptotically Improved Circuit for $d$-ary Grover's Algorithm with Advanced Decomposition of $n$-qudit Toffoli Gate
• Authors: Amit Saha, Ritajit Majumdar, Debasri Saha, Amlan Chakrabarti, Susmita Sur-Kolay
• Abstract summary: Grover's algorithm can be extended to a $d$-ary (qudit) quantum system. An $n$-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm.
• Score: 2.9923891863939938
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The progress in building quantum computers to execute quantum algorithms has recently been remarkable. Grover's search algorithm in a binary quantum system provides considerable speed-up over classical paradigm. Further, Grover's algorithm can be extended to a $d$-ary (qudit) quantum system for utilizing the advantage of larger state space, which helps to reduce the run-time of the algorithm as compared to the traditional binary quantum systems. In a qudit quantum system, an $n$-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm. In this article, a generalized $n$-qudit Toffoli gate has been realized using higher dimensional qudits to attain a logarithmic depth decomposition without ancilla qudit. The circuit for Grover's algorithm has then been designed for any $d$-ary quantum system, where $d \ge 2$, with the proposed $n$-qudit Toffoli gate to obtain optimized depth compared to earlier approaches. The technique for decomposing an $n$-qudit Toffoli gate requires access to two immediately higher energy levels, making the design susceptible to errors. Nevertheless, we show that the percentage decrease in the probability of error is significant as we have reduced both gate count and circuit depth as compared to that in state-of-the-art works.

Related papers

• Distributed Exact Generalized Grover's Algorithm [9.675088142486729]
  We propose a distributed Exactized Grover's Algorithm (DEGGA) to solve a generalized search problem. Our algorithm ensures accuracy, with a theoretical probability of identifying the target states at $100%$. Our method requires a total of $n$ qubits, eliminating the need for auxiliary qubits.
  arXiv  Detail & Related papers  (2024-05-11T09:17:11Z)
• Grover's Algorithm Offers No Quantum Advantage [0.0]
  Grover's algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. We construct a quantum inspired algorithm, executable on a classical computer, that performs Grover's task in linear number of call to the oracle. We critically examine the possibility of a practical speedup, a possibility that depends on the nature of the quantum circuit associated with the oracle.
  arXiv  Detail & Related papers  (2023-03-20T17:56:20Z)
• Distributed exact quantum algorithms for Bernstein-Vazirani and search problems [9.146620606615889]
  We give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. We provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods.
  arXiv  Detail & Related papers  (2023-03-19T14:18:49Z)
• Generalized Toffoli gate decomposition using ququints: Towards realizing Grover's algorithm with qudits [1.4732811715354455]
  We present an efficient decomposition of the generalized Toffoli gate on the five-level quantum systems, so-called ququints. Our results are applicable for quantum processors based on various physical platforms.
  arXiv  Detail & Related papers  (2022-12-23T18:05:44Z)
• Universal qudit gate synthesis for transmons [44.22241766275732]
  We design a superconducting qudit-based quantum processor. We propose a universal gate set featuring a two-qudit cross-resonance entangling gate. We numerically demonstrate the synthesis of $rm SU(16)$ gates for noisy quantum hardware.
  arXiv  Detail & Related papers  (2022-12-08T18:59:53Z)
• Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
  We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder. Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
  arXiv  Detail & Related papers  (2022-09-30T02:36:42Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Towards Demonstrating Fault Tolerance in Small Circuits Using Bacon-Shor Codes [5.352699766206807]
  We study a next step - fault-tolerantly implementing quantum circuits. We compute pseudo-thresholds for the Pauli error rate $p$ in a depolarizing noise model. We see that multiple rounds of stabilizer measurements give an improvement over performing a single round at the end.
  arXiv  Detail & Related papers  (2021-08-04T14:24:14Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.