Author name cluster

Daowen Qiu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers

1 author row

TCS Journal 2024 Journal Article

Distributed Grover's algorithm

Daowen Qiu
Le Luo
Ligang Xiao

In this paper, we propose a distributed Grover's algorithm, and it requires fewer qubits and has a linear advantage in time complexity compared to the original Grover's algorithm. More exactly, to search for a target in an unstructured database with N elements, Grover's algorithm can get the target with query complexity O ( N ), but our distributed Grover's algorithm with K computing nodes can get the target with query complexity O ( N K ), and the number of qubits inputted in our distributed Grover's algorithm is ⌊ log ⁡ K ⌋ less than that in Grover's algorithm. In addition, we propose an efficient algorithm of constructing quantum circuits for realizing the oracle corresponding to any Boolean function with conjunctive normal form (CNF).

TCS Journal 2022 Journal Article

Quantum and classical query complexities for generalized Simon's problem

Zhenggang Wu
Daowen Qiu
Jiawei Tan
Hao Li
Guangya Cai

Simon's problem is an essential example demonstrating the faster speed of quantum computers than classical computers for solving some problems. The optimal separation between exact quantum and classical query complexities for Simon's problem has been proved by Cai & Qiu. Generalized Simon's problem can be described as follows. Given a function f: { 0, 1 } n → { 0, 1 } m, with the property that there is some unknown hidden subgroup S such that f ( x ) = f ( y ) iff x ⊕ y ∈ S, for any x, y ∈ { 0, 1 } n, where | S | = 2 k for some 0 ≤ k ≤ n ( m ≥ n − k ). The goal of generalized Simon's problem is to find S. For the case of k = 1, it is Simon's problem exactly. In this paper, we propose an exact quantum algorithm with O ( n − k ) queries and an non-adaptive deterministic classical algorithm with O ( k 2 n − k ) queries for solving the generalized Simon's problem. Also, we prove that their lower bounds are Ω ( n − k ) and Ω ( k 2 n − k ), respectively. Therefore, we obtain a tight exact quantum query complexity Θ ( n − k ) and an almost tight non-adaptive classical deterministic query complexities Ω ( k 2 n − k ) ∼ O ( k 2 n − k ) for this problem.

I&C Journal 2020 Journal Article

Revisiting Deutsch-Jozsa algorithm

Daowen Qiu
Shenggen Zheng

The Deutsch-Jozsa algorithm is essentially faster than any possible deterministic classical algorithm for solving a promise problem that is in fact a symmetric partial Boolean function, named as the Deutsch-Jozsa problem. The Deutsch-Jozsa problem can be equivalently described as a partial function D J n 0: { 0, 1 } n → { 0, 1 } defined as: D J n 0 ( x ) = 1 for | x | = n / 2, D J n 0 ( x ) = 0 for | x | = 0, n, and it is undefined for the remaining cases, where n is even, and | x | is the Hamming weight of x. The Deutsch-Jozsa algorithm needs only one query to compute D J n 0 but the classical deterministic algorithm requires n 2 + 1 queries to compute it in the worse case. We present all symmetric partial Boolean functions with degree 1 and 2; We prove the exact quantum query complexity of all symmetric partial Boolean functions with degree 1 and 2. We prove Deutsch-Jozsa algorithm can compute any symmetric partial Boolean function f with exact quantum 1-query complexity.

TCS Journal 2020 Journal Article

Security improvements of several basic quantum private query protocols with O(log N) communication complexity

Fang Yu
Daowen Qiu
Xiaoming Wang
Qin Li
Lvzhou Li
Jozef Gruska

New quantum private database (with N elements) query protocols are presented and analyzed. Protocols preserve O ( log ⁡ N ) communication complexity of known protocols for the same task, but achieve several significant improvements in security, especially concerning user privacy. For example, the randomized form of our protocol has a cheat-sensitive property – it allows the user to detect a dishonest database with a nonzero probability, while the phase-encoded private query protocols [6, 7] for the same task do not have such a property. Moreover, when the database performs the computational basis measurement, a particular projective measurement which can cause a significant loss of user privacy in the previous private query protocols with O ( log ⁡ N ) communication complexity, at most half of the user privacy could leak to such a database in our protocol, while in the QPQ protocol [5], the entire user privacy could leak out. In addition, it is proved here that for large N, the user could detect a cheating via the computational basis measurement, with a probability close to 1 2 using O ( N ) special queries. Finally, it is shown here, for both forms of our protocol, basic and randomized, how a dishonest database has to act in case it could not learn user's queries.

TCS Journal 2019 Journal Article

Entangling and disentangling in Grover's search algorithm

Minghua Pan
Daowen Qiu
Paulo Mateus
Jozef Gruska

Entanglement is believed to be crucial in making quantum algorithms more powerful than their classical counterparts for certain computational tasks. In Grover's search algorithm, the Grover's operator/iteration G can be decomposed into two basic operators, i. e. , G = R O, where O is so called the Oracle operator and R is the Reflection operator. To probe the production/depletion of entanglement from basic operator level, we investigate the roles the Oracle and the Reflection operators play in the entanglement dynamics during Grover's search algorithm application. Using geometric measure of entanglement (GME), we show that the Oracle operator is an entangling operator which almost always produces (increases) entanglement while the Reflection operator is a disentangling operator which mainly depletes (decreases) entanglement. We explicitly demonstrate that there exists a turning point during the Grover's iteration application with the following properties. Before that turning point, the entanglement is almost always increased when the Oracle operator is applied, and the effect of the Reflection operator on the level of entanglement can be almost ignored. However, after the turning point, both the Oracle and the Reflection operators play important roles to the entanglement, more exactly, the Reflection operator significantly decreases entanglement while the Oracle operator increases entanglement. All these results are carefully demonstrated.

TCS Journal 2017 Journal Article

Promise problems solved by quantum and classical finite automata

Shenggen Zheng
Lvzhou Li
Daowen Qiu
Jozef Gruska

The concept of promise problems was introduced and started to be systematically explored by Even, Selman, Yacobi, Goldreich, and other scholars. It has been argued that promise problems should be seen as partial decision problems and as such that they are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory. The main purpose of this paper is to explore the promise problems accepted by classical, quantum and also semi-quantum finite automata. More specifically, we first introduce two acceptance modes of promise problems, recognizability and solvability, and explore their basic properties. Afterwards, we show several results concerning descriptional complexity on promise problems. In particular, we prove: (1) there is a promise problem that can be recognized exactly by measure-once one-way quantum finite automata (MO-1QFA), but no deterministic finite automata (DFA) can recognize it; (2) there is a promise problem that can be solved with error probability ϵ ≤ 1 / 3 by one-way finite automaton with quantum and classical states (1QCFA), but no one-way probability finite automaton (PFA) can solve it with error probability ϵ ≤ 1 / 3; and especially, (3) there are promise problems A ( p ) with size p that can be solved with any error probability by MO-1QFA with only two quantum basis states, but they can not be solved exactly by any MO-1QFA with two quantum basis states; in contrast, the minimal PFA solving A ( p ) with any error probability (usually smaller than 1/2) has p states. Finally, we mention a number of problems related to promise for further study.

TCS Journal 2016 Journal Article

Lower bounds on the size of semi-quantum finite automata

Lvzhou Li
Daowen Qiu

In the literature, there exist several interesting hybrid models of finite automata which have both quantum and classical states. We call them semi-quantum finite automata. In this paper, we compare the descriptional power of these models and DFA. Specifically, we present a uniform method that gives a lower bound on the size of the three existing main models of semi-quantum finite automata, and this bound shows that semi-quantum finite automata can be at most exponentially more concise than DFA. Compared with a recent work [4], our method has the following two advantages: (i) it is much more concise; and (ii) it is universal, since it is applicable to the three existing main models of semi-quantum finite automata, instead of only one specific model.

I&C Journal 2015 Journal Article

Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata

Shenggen Zheng
Daowen Qiu
Jozef Gruska

Interactive proof systems (IP) are very powerful – languages they can accept form exactly PSPACE. They represent also one of the very fundamental concepts of theoretical computing and a model of computation by interactions. One of the key players in IP is verifier. In the original model of IP whose power is that of PSPACE, the only restriction on verifiers is that they work in randomized polynomial time. Because of such key importance of IP, it is of large interest to find out how powerful will IP be when verifiers are more restricted. So far this was explored for the case that verifiers are two-way probabilistic finite automata (Dwork and Stockmeyer, 1990) and one-way quantum finite automata as well as two-way quantum finite automata (Nishimura and Yamakami, 2009). IP in which verifiers use public randomization is called Arthur–Merlin proof systems (AM). AM with verifiers modeled by Turing Machines augmented with a fixed-size quantum register (qAM) were studied also by Yakaryilmaz (2012). He proved, for example, that an NP-complete language L knapsack, representing the 0–1 knapsack problem, can be recognized by a qAM whose verifier is a two-way finite automaton working on quantum mixed states using superoperators. In this paper we explore the power of AM for the case that verifiers are two-way finite automata with quantum and classical states (2QCFA) – introduced by Ambainis and Watrous in 2002 – and the communications are classical. It is of interest to consider AM with such “semi-quantum” verifiers because they use only limited quantum resources. Our main result is that such Quantum Arthur–Merlin proof systems (QAM(2QCFA)) with polynomial expected running time are more powerful than the models in which the verifiers are two-way probabilistic finite automata (AM(2PFA)) with polynomial expected running time. Moreover, we prove that there is a language which can be recognized by an exponential expected running time QAM(2QCFA), but cannot be recognized by any AM(2PFA), and that the NP-complete language L knapsack can also be recognized by a QAM(2QCFA) working only on quantum pure states using unitary operators.

TCS Journal 2013 Journal Article

State succinctness of two-way finite automata with quantum and classical states

Shenggen Zheng
Daowen Qiu
Jozef Gruska
Lvzhou Li
Paulo Mateus

Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any m ∈ Z + and any ϵ < 1 / 2, we show that: 1. there is a promise problem A eq ( m ) which can be solved by a 2QCFA with one-sided error ϵ in a polynomial expected running time with a constant number (that depends neither on m nor on ε) of quantum states and O ( log 1 ϵ ) classical states, whereas the sizes of the corresponding deterministic finite automata (DFA), two-way nondeterministic finite automata (2NFA) and polynomial expected running time two-way probabilistic finite automata (2PFA) are at least 2 m + 2, log m, and ( log m ) / b 3, respectively; 2. there exists a language L twin ( m ) = { w c w | w ∈ { a, b } ⁎, | w | = m } over the alphabet Σ = { a, b, c } which can be recognized by a 2QCFA with one-sided error ϵ in an exponential expected running time with a constant number of quantum states and O ( log 1 ϵ ) classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2 m, m, and m / b 3, respectively; where b is a constant.

TCS Journal 2012 Journal Article

Characterizations of one-way general quantum finite automata

Lvzhou Li
Daowen Qiu
Xiangfu Zou
Lvjun Li
Lihua Wu
Paulo Mateus

Generally, unitary transformations limit the computational power of quantum finite automata (QFA). In this paper, we study a generalized model named one-way general quantum finite automata (1gQFA), in which each symbol in the input alphabet induces a trace-preserving quantum operation, instead of a unitary transformation. Two different kinds of 1gQFA will be studied: measure-once one-way general quantum finite automata (MO-1gQFA) where a measurement deciding to accept or reject is performed at the end of a computation, and measure-many one-way general quantum finite automata (MM-1gQFA) where a similar measurement is performed after each trace-preserving quantum operation on reading each input symbol. We characterize the measure-once model from three aspects: the closure property, the language recognition power, and the equivalence problem. We prove that MO-1gQFA recognize, with bounded error, precisely the set of all regular languages. Our results imply that some models of quantum finite automata proposed in the literature, which were expected to be more powerful, still cannot recognize non-regular languages. We prove that MM-1gQFA also recognize only regular languages with bounded error. Thus, MM-1gQFA and MO-1gQFA have the same language recognition power, in sharp contrast with traditional MO-1QFA and MM-1QFA, the former being strictly less powerful than the latter. Finally, we present a necessary and sufficient condition for two MM-1gQFA to be equivalent.

I&C Journal 2012 Journal Article

On the complexity of minimizing probabilistic and quantum automata

Paulo Mateus
Daowen Qiu
Lvzhou Li

Several types of automata, such as probabilistic and quantum automata, require to work with real and complex numbers. For such automata the acceptance of an input is quantified with a probability. There are plenty of results in the literature addressing the complexity of checking the equivalence of these automata, that is, checking whether two automata accept all inputs with the same probability. On the other hand, the critical problem of finding the minimal automata equivalent to a given one has been left open [C. Moore, J. P. Crutchfield, Quantum automata and quantum grammars, Theoret. Comput. Sci. 237 (2000) 275–306, see p. 304, Problem 5]. In this work, we reduce the minimization problem of probabilistic and quantum automata to finding a solution of a system of algebraic polynomial (in)equations. An EXPSPACE upper bound on the complexity of the minimization problem is derived by applying Renegarʼs algorithm. More specifically, we show that the state minimization of probabilistic automata, measure-once quantum automata, measure-many quantum automata, measure-once generalized quantum automata, and measure-many generalized quantum automata is decidable and in EXPSPACE. Finally, we also solve an open problem concerning minimal covering of stochastic sequential machines [A. Paz, Introduction to Probabilistic Automata, Academic Press, New York, 1971, p. 43].

TCS Journal 2009 Journal Article

A note on quantum sequential machines

Lvzhou Li
Daowen Qiu

Quantum sequential machines (QSMs) are a quantum version of stochastic sequential machines (SSMs). Recently, we showed that two QSMs M 1 and M 2 with n 1 and n 2 states, respectively, are equivalent iff they are ( n 1 + n 2 ) 2 -equivalent [L. Z. Li, D. W. Qiu, Determination of equivalence between quantum sequential machines, Theoretical Computer Science 358 (2006) 65–74]. However, using this result to check the equivalence is likely to need exponential expected time. In this note, we consider the time complexity of deciding the equivalence between QSMs and related problems. The main results are as follows: (1) We present a polynomial-time algorithm for deciding the equivalence between QSMs, and, if two QSMs are not equivalent, this algorithm will produce an input–output pair with length not more than ( n 1 + n 2 ) 2. (2) We improve the bound for the equivalence between QSMs from ( n 1 + n 2 ) 2 to n 1 2 + n 2 2 − 1, by employing Moore and Crutchfield’s method [C. Moore, J. P. Crutchfield, Quantum automata and quantum grammars, Theoretical Computer Science 237 (2000) 275–306. Also quant-ph/9707031, 1997]. In addition, by viewing MO-1QFAs as a special case of QSMs, we briefly discuss the equivalence between MO-1QFAs, where the method used and the result obtained are slightly different from those given by Koshiba [T. Koshiba, Polynomial-time algorithms for the equivalence for one-way quantum finite automata, in: Proceedings of the 12th International Symposium on Algorithms and Computation, ISAAC’2001, Christchurch, New Zealand, in: Lecture Notes in Computer Science, vol. 2223, Springer, Berlin, 2001, pp. 268–278].

TCS Journal 2009 Journal Article

Hierarchy and equivalence of multi-letter quantum finite automata

Daowen Qiu
Sheng Yu

Multi-letter quantum finite automata (QFAs) are a new one-way QFA model proposed recently by Belovs, Rosmanis, and Smotrovs [A. Belovs, A. Rosmanis, J. Smotrovs, Multi-letter reversible and quantum finite automata, in: Proceedings of the 13th International Conference on Developments in Language Theory, DLT’2007, Harrachov, Czech Republic, in: Lecture Notes in Computer Science, vol. 4588, Springer, Berlin, 2007, pp. 60–71], and they showed that multi-letter QFAs can accept with no error some regular languages ( ( a + b ) ∗ b ) that are unacceptable by the one-way QFAs. In this paper, we continue to study multi-letter QFAs. We mainly focus on two issues: (1) we show that ( k + 1 ) -letter QFAs are computationally more powerful than k -letter QFAs, that is, ( k + 1 ) -letter QFAs can accept some regular languages that are unacceptable by any k -letter QFA. A comparison with the one-way QFAs is made by some examples; (2) we prove that a k 1 -letter QFA A 1 and another k 2 -letter QFA A 2 are equivalent, if and only if, they are ( n 1 + n 2 ) 4 + k − 1 -equivalent, and the time complexity of determining the equivalence of two multi-letter QFAs using this method is O ( n 12 + k 2 n 4 + k n 8 ), where n 1 and n 2 are the numbers of states of A 1 and A 2, respectively, and k = max ( k 1, k 2 ). Some other issues are addressed for further consideration.

TCS Journal 2008 Journal Article

Determining the equivalence for one-way quantum finite automata

Lvzhou Li
Daowen Qiu

Two quantum finite automata are equivalent if for any input string x the two automata accept x with equal probability. In this paper, we first focus on determining the equivalence for one-way quantum finite automata with control language (CL-1QFAs) defined by Bertoni et al. , and then, as an application, we address the equivalence problem for measure-many one-way quantum finite automata (MM-1QFAs) introduced by Kondacs and Watrous. More specifically, we obtain that: (i) Two CL-1QFAs A 1 and A 2 with control languages (regular languages) L 1 and L 2, respectively, are equivalent if and only if they are ( c 1 n 1 2 + c 2 n 2 2 − 1 ) -equivalent, where n 1 and n 2 are the numbers of states in A 1 and A 2, respectively, and c 1 and c 2 are the numbers of states in the minimal DFAs that recognize L 1 and L 2, respectively. Furthermore, if L 1 and L 2 are given in the form of DFAs, with m 1 and m 2 states, respectively, then there exists a polynomial-time algorithm running in time O ( ( m 1 n 1 2 + m 2 n 2 2 ) 4 ) that takes as input A 1 and A 2 and determines whether they are equivalent. (ii) (As an application of item (i)): Two MM-1QFAs A 1 and A 2 with n 1 and n 2 states, respectively, are equivalent if and only if they are ( 3 n 1 2 + 3 n 2 2 − 1 ) -equivalent. Furthermore, there is a polynomial-time algorithm running in time O ( ( 3 n 1 2 + 3 n 2 2 ) 4 ) that takes as input A 1 and A 2 and determines whether A 1 and A 2 are equivalent.

AIJ Journal 2007 Journal Article

A note on Trillas' CHC models

Daowen Qiu

Trillas et al. [E. Trillas, S. Cubillo, E. Castiñeira, On conjectures in orthocomplemented lattices, Artificial Intelligence 117 (2000) 255–275] recently proposed a mathematical model for conjectures, hypotheses and consequences (abbr. CHCs), and with this model we can execute certain mathematical reasoning and reformulate some important theorems in classical logic. We demonstrate that the orthomodular condition is not necessary for holding Watanabe's structure theorem of hypotheses, and indeed, in some orthocomplemented but not orthomodular lattices, this theorem is still valid. We use the CHC operators to describe the theorem of deduction, the theorem of contradiction and the Lindenbaum theorem of classical logic, and clarify their existence in the CHC models; a number of examples is presented. And we re-define the CHC operators in residuated lattices, and particularly reveal the essential differences between the CHC operators in orthocomplemented lattices and residuated lattices.

TCS Journal 2007 Journal Article

Automata theory based on quantum logic: Reversibilities and pushdown automata

Daowen Qiu

Automata theory based on quantum logic, called l -valued finite automata ( l -VFAs), may be viewed as a logical approach to quantum computing. This work is mainly divided into two parts: one part deals with reversibility of l -VFAs, and the other establishes a basic framework of l -valued pushdown automata ( l -VPDAs). First we provide some preliminaries concerning quantum logic and l -VFAs, and we prove a useful property of l -valued successor and source operators. Then we clarify the relationships between various reversibilities closely related to quantum finite automata in the literature. In particular, we define a reversibility of l -VFAs which is termed as retrievability, and we clarify the relationships between a number of different fashions regarding retrievability of l -VFAs. We prove that some of them are equivalent, but for the others to be equivalent the truth-value set is required to satisfy a certain condition. This is an essential difference from the classical situation. Afterwards, we introduce l -VPDAs and show that the class of the languages accepted by l -VPDAs by empty stack coincides with that accepted by l -VPDAs by final state. Finally, we provide some examples of l -VFAs and conclude with some remarks.

TCS Journal 2006 Journal Article

Determination of equivalence between quantum sequential machines

Lvzhou Li
Daowen Qiu

Quantum sequential machines (QSMs) that may be viewed as a quantum variant of stochastic sequential machines (SSMs) are one of the important quantum computing models. A very crucial result on SSMs is that two SSMs with n and n ′ states, respectively, and the same input and output alphabets are equivalent if and only if they are ( n + n ′ - 1 ) -equivalent. Therefore, Gudder asked whether or not it holds for QSMs, as an open problem in this direction, since the further study is closely related to this result. Qiu demonstrated that in QSMs this result does not hold, and therefore answered in part the problem. However, as Qiu indicated, the sufficient and necessary conditions for the equivalence between two QSMs are still not discovered. In this paper, we show that if the condition of ( n + n ′ - 1 ) -equivalence is appropriately relaxed, then we can give a sufficient and necessary condition for justifying the equivalence between two QSMs. More precisely, we show that any two QSMs M and M ′ are equivalent if and only if they are ( n + n ′ ) 2 -equivalent, where n and n ′ are, respectively, the numbers of states in M and M ′. We therefore solve the open problem suggested by Gudder, and provide a basic result for further developing QSMs. As well, we discuss strongly factorizable QSMs and present the conditions for the equivalence between two strongly factorizable QSMs.

I&C Journal 2004 Journal Article

Automata theory based on quantum logic: some characterizations

Daowen Qiu

Automata theory based on quantum logic (abbr. l-valued automata theory) may be viewed as a logical approach of quantum computation. In this paper, we characterize some fundamental properties of l-valued automata theory, and discover that some properties of the truth-value lattices of the underlying logic are equivalent to certain properties of automata. More specifically (i) the transition relations of l-valued automata are extended to describe the transitions enabled by strings of input symbols, and particularly, these extensions depend on the distributivity of the truth-value lattices (Proposition 3. 1); (ii) some properties of the l-valued successor and source operators and l-valued subautomata are demonstrated to be equivalent to a property of the truth-value lattices which is exactly equivalent to the distributive law (Proposition 4. 3 and Corollary 4. 4). This is a new characterization of Boolean algebras in the framework of l-valued automata theory; (iii) we verify that the intersection of two l-valued subautomata is still an l-valued subautomaton if and only if the multiplication (&) is distributive over the union in the truth-value lattices (Proposition 4. 5), which is strictly weaker than the usual distributivity; (iv) we show that some topological characterizations in terms of the l-valued successor and source operators also rely on the distributivity of truth-value lattices (Theorem 5. 6). Finally, we address some related topics for further study.

TCS Journal 2004 Journal Article

Characterizations of quantum automata

Daowen Qiu
Mingsheng Ying

We define q quantum finite automata (qQFAs) and q quantum regular grammars (qQRGs), and verify that they are exactly equivalent to those measure-once quantum finite automata (MO-QFAs) in the literature. In particular, we define q quantum pushdown automata (qQPDAs) and QPDAs that are at least as powerful as those defined by Moore and Crutchfield, and especially we focus on demonstrating the equivalence between qQPDAs and QPDAs. Also, we discuss some of the properties of languages accepted by qQPDAs; for example, every cut-point language accepted by qQPDA is independent of the cut-point.