D 2014

From Quantum Query Complexity to State Complexity

ZHENG, Shenggen and Daowen QIU

Basic information

Original name

From Quantum Query Complexity to State Complexity

Authors

ZHENG, Shenggen (156 China, guarantor, belonging to the institution) and Daowen QIU (156 China)

Edition

Switzerland, Computing with New Resources, p. 231-245, 15 pp. 2014

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/14:00079998

Organization unit

Faculty of Informatics

ISBN

978-3-319-13349-2

ISSN

DOI

UT WoS

000355015600019

Keywords in English

General method; Quantum finite automata; Quantum query complexity; Query complexity; State complexity
Změněno: 27/4/2015 14:15, RNDr. Pavel Šmerk, Ph.D.

Abstract

V originále

State complexity of quantum finite automata is one of the interesting topics in studying the power of quantum finite automata. It is therefore of importance to develop general methods how to show state succinctness results for quantum finite automata. One such method is presented and demonstrated in this paper. In particular, we show that state succinctness results can be derived out of query complexity results.

Links

EE2.3.30.0009, research and development project
Name: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci