GAPs for Shallow Implementation of Quantum Finite Automata

• URL: http://arxiv.org/abs/2304.12868v3
• Date: Wed, 6 Sep 2023 06:21:38 GMT
• Title: GAPs for Shallow Implementation of Quantum Finite Automata
• Authors: Mansur Ziiatdinov, Aliya Khadieva, Abuzer Yakary{\i}lmaz
• Abstract summary: Quantum fingerprinting maps a word of length N to a state of O(log N) qubits. Quantum fingerprinting is useful in quantum algorithms, communication, and cryptography. computing quantum fingerprint using all available qubits of the current quantum computers is infeasible.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum fingerprinting is a technique that maps classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses less resources, making it useful in quantum algorithms, communication, and cryptography. One of the examples of quantum fingerprinting is quantum automata algorithms for MOD_p languages, where p is a prime number. However, implementing such an automaton on the current quantum hardware is not efficient. Quantum fingerprinting maps a word of length N to a state of O(log N) qubits, and uses O(N) unitary operations. Computing quantum fingerprint using all available qubits of the current quantum computers is infeasible due to a large number of quantum operations. To make quantum fingerprinting practical, we should optimize the circuit for depth instead of width in contrast to the previous works. We propose explicit methods of quantum fingerprinting based on tools from additive combinatorics, such as generalized arithmetic progressions (GAPs), and prove that these methods provide circuit depth comparable to a probabilistic method. We also compare our method to prior work on explicit quantum fingerprinting methods.

Related papers

• Quantum Information Processing with Molecular Nanomagnets: an introduction [49.89725935672549]
  We provide an introduction to Quantum Information Processing, focusing on a promising setup for its implementation. We introduce the basic tools to understand and design quantum algorithms, always referring to their actual realization on a molecular spin architecture. We present some examples of quantum algorithms proposed and implemented on a molecular spin qudit hardware.
  arXiv  Detail & Related papers  (2024-05-31T16:43:20Z)
• Realization of quantum algorithms with qudits [0.7892577704654171]
  We review several ideas indicating how multilevel quantum systems, also known as qudits, can be used for efficient realization of quantum algorithms. We focus on techniques of leveraging qudits for simplifying decomposition of multiqubit gates, and for compressing quantum information by encoding multiple qubits in a single qudit. These theoretical schemes can be implemented with quantum computing platforms of various nature, such as trapped ions, neutral atoms, superconducting junctions, and quantum light.
  arXiv  Detail & Related papers  (2023-11-20T18:34:19Z)
• 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)
• A hybrid quantum image edge detector for the NISQ era [62.997667081978825]
  We propose a hybrid method for quantum edge detection based on the idea of a quantum artificial neuron. Our method can be practically implemented on quantum computers, especially on those of the current noisy intermediate-scale quantum era.
  arXiv  Detail & Related papers  (2022-03-22T22:02:09Z)
• Revisiting dequantization and quantum advantage in learning tasks [3.265773263570237]
  We show that classical algorithms with sample and query (SQ) access can accomplish some learning tasks exponentially faster than quantum algorithms with quantum state inputs. Our findings suggest that the absence of exponential quantum advantage in some learning tasks may be due to SQ access being too powerful relative to quantum state inputs.
  arXiv  Detail & Related papers  (2021-12-01T20:05:56Z)
• Efficient realization of quantum algorithms with qudits [0.70224924046445]
  We propose a technique for an efficient implementation of quantum algorithms with multilevel quantum systems (qudits) Our method uses a transpilation of a circuit in the standard qubit form, which depends on the parameters of a qudit-based processor. We provide an explicit scheme of transpiling qubit circuits into sequences of single-qudit and two-qudit gates taken from a particular universal set.
  arXiv  Detail & Related papers  (2021-11-08T11:09:37Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• 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)
• Efficient CNOT Synthesis for NISQ Devices [1.0152838128195467]
  In the era of noisy intermediate-scale quantum (NISQ), executing quantum algorithms on actual quantum devices faces unique challenges. We propose a CNOT synthesis method called the token reduction method to solve this problem. Our algorithm consistently outperforms the best publicly accessible algorithm for all of the tested quantum architectures.
  arXiv  Detail & Related papers  (2020-11-12T15:13:32Z)
• Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions [0.8315657895474382]
  We show that there exist families of quantum states that can be prepared to high precision with circuits of linear size and depth. We further develop an algorithm that requires only linear classical time to generate accurate linear-depth circuits.
  arXiv  Detail & Related papers  (2020-05-09T02:31:44Z)
• 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.