Fault-Tolerant Implementation of the Deutsch-Jozsa Algorithm

• URL: http://arxiv.org/abs/2412.04791v1
• Date: Fri, 06 Dec 2024 05:55:31 GMT
• Title: Fault-Tolerant Implementation of the Deutsch-Jozsa Algorithm
• Authors: Divyanshu Singh, Shiroman Prakash,
• Abstract summary: The Deutsch-Josza algorithm is a natural candidate for small fault-tolerance experiments. We implement the algorithm on a trapped-ion quantum computer with and without fault-tolerant encoding. Averaged across all oracles, the reduction in error rate was nearly $90 %$.
• Score: 0.46040036610482665
• License:
• Abstract: The Deutsch-Josza algorithm, one of the first and simplest quantum algorithms, is a natural candidate for small fault-tolerance experiments. We show that one can implement the Deutsch-Josza algorithm in a fault-tolerant manner using the smallest quantum error-detecting code -- the $[[4,2,2]]$ code -- without any ancillae. We implemented the algorithm on a trapped-ion quantum computer with and without fault-tolerant encoding and compared the results. With approximately $99 \%$ confidence, we found that the fault-tolerant implementation provides a noise reduction for all oracles. Averaged across all oracles, the reduction in error rate was nearly $90 \%$.

Related papers

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
  arXiv  Detail & Related papers  (2025-02-13T12:04:39Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Practical implementation of a single-qubit rotation algorithm [0.0]
  The Toffoli is an important universal quantum gate, and will alongside the Clifford gates be available in future Fault-Tolerant Quantum Computing hardware. We evaluate the performance of a recently proposed single-qubit rotation algorithm using the Clifford+Toffoli gate set.
  arXiv  Detail & Related papers  (2024-10-24T13:53:21Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Viderman's algorithm for quantum LDPC codes [13.916368399461895]
  We present a generalization of Viderman's algorithm to quantum LDPC codes. This is the first erasure-conversion algorithm that can correct up to $Omega(D)$ errors for constant-rate quantum LDPC codes.
  arXiv  Detail & Related papers  (2023-10-11T20:17:21Z)
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem [4.555392897705548]
  Deutsch's algorithm is the first quantum algorithm to show the advantage over the classical algorithm. We propose a new quantum algorithm with indefinite causal order to solve this problem.
  arXiv  Detail & Related papers  (2023-05-09T13:04:28Z)
• 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)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• On proving the robustness of algorithms for early fault-tolerant quantum computers [0.0]
  We introduce a randomized algorithm for the task of phase estimation and give an analysis of its performance under two simple noise models. We calculate that the randomized algorithm can succeed with arbitrarily high probability as long as the required circuit depth is less than 0.916 times the dephasing scale.
  arXiv  Detail & Related papers  (2022-09-22T21:28:12Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)

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.