GAPs for Shallow Implementation of Quantum Finite Automata

DOI10.4204/EPTCS.386.21MaRDI QIDQ6204142zbMATH OpenOpenAlexFDO

Authors Aliya Khadieva, Abuzer Yakaryılmaz

Publication date 9 April 2024

Published in Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: Quantum fingerprinting is a technique that maps classical input word to a quantum state. The resulting quantum state is much shorter than original word, and its processing requires less resources, making it useful in quantum algorithms, communication and cryptography. One of the examples of quantum fingerprinting is quantum automaton for $MO{D}_p=a^{icdotp}midigeq0$ language, where $p$ is a prime number. However, implementing this automata in current quantum hardware is not efficient. Quantum fingeprinting maps a word $xin{0,1}^n$ of length $n$ to a state $|psi(x)angle$ of $O(loglogn)$ qubits, and requires $O(logn)$ unitary operations. Computing quantum fingerprint using all memory of the current quantum computers is currently infeasible due to the large number of quantum operations necessary. In order to make quantum fingerprinting practical, we must optimize the circuit for depth instead of width as previous works did. 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 probabilistic method. We also compare our method to prior work on explicit quantum fingerprinting methods.

Cites work

• Additive combinatorics
• Automata and quantum computing
• Constructing Small Sets that are Uniform in Arithmetic Progressions
• Construction of a Thin Set with small Fourier Coefficients
• Coordinate descent algorithms
• Deterministic construction of QFAs based on the quantum fingerprinting technique
• Improved constructions of quantum automata
• Quantum automata and quantum grammars
• Quantum finite automata: a modern introduction

Cited in

(1)

• A representative framework for implementing quantum finite automata on real devices

This page was built for publication: GAPs for Shallow Implementation of Quantum Finite Automata

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