Representation of Unary Singleton Languages using Quantum Finite State Automata

양자 오토마타(quantum finite-state automaton, QFA)는 각 상태를 유한한 수의 큐비트(qubit)로 표현하는 오토마타다. QFA는 확률에 따라 문자열을 수락하거나 거부하며, QFA가 인식하는 언어는 해당 QFA가 임계값 이상의 확률로 수락하는 문자열의 집합이다. 본 논문에서는 다수측정(measure-many, MM-) QFA가 유계 단측오류(bounded one-sided error)를 통해 언어를 정의하는 경우, 모든 단항(unary) 한원소(singleton) 언어에 대하여 이를 정의하는 크기 4의 MM-QFA가 존재함을 보인다. 또한 이 경우에 상수 크기의 오류발생 확률을 보장하기 위한 QFA의 수행횟수를 제시한다.

Authors

Publication Details

Journal
KIISE Transactions on Computing Practices
Published
2025-03-25
DOI
https://doi.org/10.5626/ktcp.2025.31.3.117
Primary Topic
Quantum Computing Algorithms and Architecture
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Representation of Unary Singleton Languages using Quantum Finite State Automata

Yo-Sub Han, Sicheol Sung
KIISE Transactions on Computing Practices
Quantum Computing Algorithms and Architecture
article

Representation of Unary Singleton Languages using Quantum Finite State Automata

Yo-Sub Han, Sicheol Sung
article en

Abstract

양자 오토마타(quantum finite-state automaton, QFA)는 각 상태를 유한한 수의 큐비트(qubit)로 표현하는 오토마타다. QFA는 확률에 따라 문자열을 수락하거나 거부하며, QFA가 인식하는 언어는 해당 QFA가 임계값 이상의 확률로 수락하는 문자열의 집합이다. 본 논문에서는 다수측정(measure-many, MM-) QFA가 유계 단측오류(bounded one-sided error)를 통해 언어를 정의하는 경우, 모든 단항(unary) 한원소(singleton) 언어에 대하여 이를 정의하는 크기 4의 MM-QFA가 존재함을 보인다. 또한 이 경우에 상수 크기의 오류발생 확률을 보장하기 위한 QFA의 수행횟수를 제시한다.

KIISE Transactions on Computing PracticesVol. 31(3)
Openalex Percentile: Top 98%
Quantum Computing Algorithms and Architecture
DOISourceOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Representation of Unary Singleton Languages using Quantum Finite State Automata — Yo-Sub Han, Sicheol Sung · KIISE Transactions on Computing Practices (2025) | TGRS Research Map | TGRS