Scholarlink

<p>We develop translation techniques from an NFA to a quantum circuit to validate the correctness of a system modeled by an NFA—a problem that is computationally intractable on conventional computers. Specifically, we solve a model validation problem in three steps. First, we translate a given NFA into an equivalent <i>Quantum Finite-state Automaton</i> (QFA) such that it accepts or rejects all bounded strings in their superposition and synthesize a quantum circuit for the QFA. Second, we extend the QFA circuit to simulate the time evolution of quantum states under a Hamiltonian that represents the acceptance of strings. Finally, using QAOA, we amplify the amplitudes of accepted strings so that they are measured more frequently. In addition, we apply Grover’s search algorithm for the accepted strings and compare the results with those of QAOA. Our work represents the first proposal to apply quantum computing to the problem of verifying conventional systems; our approach would facilitate software verification, program analysis, protocol design, and verification of circuits, among other applications.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A finite state automaton for quantum computing

  • 期刊论文

  • 发表日期：

    2026年1月12日

查看全文
  • YoungMin Kwon,
  • Gul Agha

摘要

We develop translation techniques from an NFA to a quantum circuit to validate the correctness of a system modeled by an NFA—a problem that is computationally intractable on conventional computers. Specifically, we solve a model validation problem in three steps. First, we translate a given NFA into an equivalent Quantum Finite-state Automaton (QFA) such that it accepts or rejects all bounded strings in their superposition and synthesize a quantum circuit for the QFA. Second, we extend the QFA circuit to simulate the time evolution of quantum states under a Hamiltonian that represents the acceptance of strings. Finally, using QAOA, we amplify the amplitudes of accepted strings so that they are measured more frequently. In addition, we apply Grover’s search algorithm for the accepted strings and compare the results with those of QAOA. Our work represents the first proposal to apply quantum computing to the problem of verifying conventional systems; our approach would facilitate software verification, program analysis, protocol design, and verification of circuits, among other applications.