Quantum finite automata can be used for pattern recognition. Present implementations on actual quantum devices face decoherence issues, which compromise the quality of long strings computation. In this work, we focus on the Measure Once 1-way Quantum Finite Automata (MO1QFA) model for addressing the MOD^p problem, investigating how quantum errors may affect the quality of the computation in this model when implemented in IBM-Q superconducting environment. To improve the performance of the implementation, we use pulse-level programming for calibrating a fast single-qubit gate designed specifically for the automaton implementation. The demonstrations conducted on the Jakarta quantum computer show that using custom pulses significantly reduces errors during extended word computations. While realizing improvements in error variations and predictability -- with a fourfold reduction in circuit latency -- the proposed solution demonstrates a substantial increase in the supported computation length of the automaton. When considering thresholds of 10% and 20% in absolute errors of acceptance probabilities, the solution has the potential to increase the maximum word length by 12 and 7+ times, respectively, compared to the default Qiskit gate.
Quantum finite automata can be used for pattern recognition. Present implementations on actual quantum devices face decoherence issues, which compromise the quality of long strings computation. In this work, we focus on the Measure Once 1-way Quantum Finite Automata (MO1QFA) model for addressing the MOD^p problem, investigating how quantum errors may affect the quality of the computation in this model when implemented in IBM-Q superconducting environment. To improve the performance of the implementation, we use pulse-level programming for calibrating a fast single-qubit gate designed specifically for the automaton implementation. The demonstrations conducted on the Jakarta quantum computer show that using custom pulses significantly reduces errors during extended word computations. While realizing improvements in error variations and predictability -- with a fourfold reduction in circuit latency -- the proposed solution demonstrates a substantial increase in the supported computation length of the automaton. When considering thresholds of 10% and 20% in absolute errors of acceptance probabilities, the solution has the potential to increase the maximum word length by 12 and 7+ times, respectively, compared to the default Qiskit gate.
Quantum fingerprinting is a technique that maps a classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses fewer resources, making it useful in quantum algorithms, communication, and cryptography. One of the examples of quantum fingerprinting is the quantum automata algorithm for M O D p = { a i · p ∣ i ≥ 0 } languages, where p is a prime number. However, implementing such an automaton on current quantum hardware is not efficient. Quantum fingerprinting maps a word x ∈{0, 1} n of length n to a state |ψ( x )〉 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 many 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. We provide a series of numerical experiments with implementation of the quantum automata for MOD 17 language on noisy simulators of IBMQ quantum devices. We show that shallow implementation based on GAPs produces results with much smaller computational error compared to standard deep circuit implementation. Despite the fact that on the ideal quantum computational device, the opposite situation arises. We show that the shallow circuit for the quantum automaton is better for near-future quantum computational devices.
A quantum finite-state automaton (QFA) is a theoretical model designed to simulate the evolution of a quantum system with finite memory in response to sequential input strings. We define the language of a QFA as the set of strings that lead the QFA to an accepting state when processed from its initial state. QFAs exemplify how quantum computing can achieve greater efficiency compared to classical computing. While being one of the simplest quantum models, QFAs are still notably challenging to construct from scratch due to the preliminary knowledge of quantum mechanics required for superimposing unitary constraints on the automata. Furthermore, even when QFAs are correctly assembled, the limitations of a current quantum computer may cause fluctuations in the simulation results depending on how an assembled QFA is translated into a quantum circuit. We present a framework that provides a simple and intuitive way to build QFAs and maximize the simulation accuracy. Our framework relies on two methods: First, it offers a predefined construction for foundational types of QFAs that recognize special languages MOD and EQU. They play a role of basic building blocks for more complex QFAs. In other words, one can obtain more complex QFAs from these foundational automata using standard language operations. Second, we improve the simulation accuracy by converting these QFAs into quantum circuits such that the resulting circuits perform well on noisy quantum computers. Our framework is available at https://github.com/sybaik1/qfa-toolkit.
The 2-way quantum finite automaton introduced by Kondacs and Watrous [Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75] can accept nonregular languages with bounded error in polynomial time. If we restrict the head of the automaton to moving classically and to moving only in one direction, the acceptance power of this 1-way quantum finite automaton is reduced to a proper subset of the regular languages. In this paper we study two different models of 1-way quantum finite automata. The first model, termed measure-once quantum finite automata, was introduced by Moore and Crutchfield [Theoret. Comput. Sci., 237 (2000), pp. 275--306], and the second model, termed measure-many quantum finite automata, was introduced by Kondacs and Watrous [Proceedings of the38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75]. We characterize the measure-once model when it is restricted to accepting with bounded error and show that, without that restriction, it can solve the word problem over the free group. We also show that it can be simulated by a probabilistic finite automaton and describe an algorithm that determines if two measure-once automata are equivalent. We prove several closure properties of the classes of languages accepted by measure-many automata, including inverse homomorphisms, and provide a new necessary condition for a language to be accepted by the measure-many model with bounded error. Finally, we show that piecewise testable sets can be accepted with bounded error by a measure-many quantum finite automaton, introducing new construction techniques for quantum automata in the process.
We describe an experimental effort designing and deploying error-robust single-qubit operations using a cloud-based quantum computer and analog-layer programming access. We design numerically optimized pulses that implement target operations and exhibit robustness to various error processes including dephasing noise, instabilities in control amplitudes, and crosstalk. Pulse optimization is performed using a flexible optimization package incorporating a device model and physically relevant constraints (e.g., bandwidth limits on the transmission lines of the dilution refrigerator housing IBM Quantum hardware). We present techniques for conversion and calibration of physical Hamiltonian definitions to pulse waveforms programmed via Qiskit Pulse and compare performance against hardware default derivative removal by adiabatic gate (DRAG) pulses on a five-qubit device. Experimental measurements reveal default DRAG pulses exhibit coherent errors an order of magnitude larger than tabulated randomized-benchmarking measurements; solutions designed to be robust against these errors outperform hardware-default pulses for all qubits across multiple metrics. Experimental measurements demonstrate performance enhancements up to: about a 10 times single-qubit gate coherent-error reduction; about a 5 times average coherent-error reduction across a five-qubit system; about a 10 times increase in calibration window to one week of valid pulse calibration; about a 12 times reduction gate-error variability across qubits and over time; and up to about a 9 times reduction in single-qubit gate error (including crosstalk) in the presence of fully parallelized operations. Randomized benchmarking reveals error rates for Clifford gates constructed from optimized pulses consistent with tabulated T1 limits, and demonstrates a narrowing of the distribution of outcomes over randomizations associated with suppression of coherent errors.
The quantum circuit model is an abstraction that hides the underlying physical implementation of gates and measurements on a quantum computer. For precise control of real quantum hardware, the ability to execute pulse and readout-level instructions is required. To that end, we introduce Qiskit Pulse, a pulse-level programming paradigm implemented as a module within Qiskit-Terra [ 1 ]. To demonstrate the capabilities of Qiskit Pulse, we calibrate both un-echoed and echoed variants of the cross-resonance entangling gate with a pair of qubits on an IBM Quantum system accessible through the cloud. We perform Hamiltonian characterization of both single and two-pulse variants of the cross-resonance entangling gate with varying amplitudes on a cloud-based IBM Quantum system. We then transform these calibrated sequences into a high-fidelity CNOT gate by applying pre and post local-rotations to the qubits, achieving average gate fidelities of F = 0.981 and F = 0.979 for the un-echoed and echoed respectively. This is comparable to the standard backend CNOT fidelity of F CX = 0.984. Furthermore, to illustrate how users can access their results at different levels of the readout chain, we build a custom discriminator to investigate qubit readout correlations. Qiskit Pulse allows users to explore advanced control schemes such as optimal control theory, dynamical decoupling, and error mitigation that are not available within the circuit model.
We present an explicit embedding of measure-once quantum finite automata (MO-QFAs) into the Feynman quantum computer model.Given an MO-QFA, we construct the corresponding Feynman machine whose register encodes both the input word and the automaton state, while a cursor evolving under a Hamiltonian implements the sequential application of the automaton transition operators.The construction relies on nested SWITCH mechanisms that select transitions according to the input symbols.We prove that, for every MO-QFA and every input word, measuring the cursor in its final position yields exactly the quantum state reached by the automaton after processing the same input.Consequently, acceptance probabilities are preserved exactly, and every language recognized by an MO-QFA with cutpoint can be recognized within the Feynman framework with the same acceptance behavior.This establishes an explicit connection between discrete-time quantum computation and continuous-time, physically motivated Hamiltonian models.