BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Lvzhou Li

Lvzhou Li appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phFormal Languages and Automata TheoryComputational ComplexityCryptography and SecurityLogic in Computer ScienceMachine Learning

Catalog footprint

What is connected

25works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

25 published item(s)

preprint2026arXiv

Optimal qudit overlapping tomography and optimal measurement order

Quantum state tomography is essential for characterizing quantum systems, but it becomes infeasible for large systems due to exponential resource scaling. Overlapping tomography addresses this challenge by reconstructing all $k$-body marginals using few measurement settings, enabling the efficient extraction of key information for many quantum tasks. While optimal schemes are known for qubits, the extension to higher-dimensional qudit systems remains largely unexplored. Here, we investigate optimal qudit overlapping tomography, constructing local measurement settings from generalized Gell-Mann matrices. By establishing a correspondence with combinatorial covering arrays, we present two explicit constructions of optimal measurement schemes. For $n$-qutrit systems, we prove that pairwise tomography requires at most $8 + 56\left\lceil \log_{8} n \right\rceil$ measurement settings, and provide an explicit scheme achieving this bound. Furthermore, we develop an efficient algorithm to determine the optimal order of these measurement settings, minimizing the experimental overhead associated with switching configurations. Compared to the worst-case ordering, our optimized schedule reduces switching costs by approximately 50\%. These results provide a practical pathway for efficient characterization of qudit systems, facilitating their application in quantum communication and computation.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantum algorithm for learning secret strings and its experimental demonstration

In this paper, we consider the secret-string-learning problem in the teacher-student setting: the teacher has a secret string $s\in {\{0,1\}^{n}}$, and the student wants to learn the secret $s$ by question-answer interactions with the teacher, where at each time, the student can ask the teacher with a pair $(x, q) \in {\{0,1\}^{n}}\times\{0,1,\cdots, n-1\}$ and the teacher returns a bit given by the oracle $f_{s}(x,q)$ that indicates whether the length of the longest common prefix of $s$ and $x$ is greater than $q$ or not. Our contributions are as follows. (i) We prove that any classical deterministic algorithm needs at least $n$ queries to the oracle $f_{s}$ to learn the $n$-bit secret string $s$ in both the worst case and the average case, and also present an optimal classical deterministic algorithm learning any $s$ using $n$ queries. (ii) We obtain a quantum algorithm learning the $n$-bit secret string $s$ with certainty using $\left\lceil n/2\right\rceil$ queries to the oracle $f_s$, thus proving a double speedup over classical counterparts. (iii) Experimental demonstrations of our quantum algorithm on the IBM cloud quantum computer are presented, with average success probabilities of $85.3\%$ and $82.5\%$ for all cases with $n=2$ and $n=3$ , respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantum Algorithm for Online Convex Optimization

We explore whether quantum advantages can be found for the zeroth-order online convex optimization problem, which is also known as bandit convex optimization with multi-point feedback. In this setting, given access to zeroth-order oracles (that is, the loss function is accessed as a black box that returns the function value for any queried input), a player attempts to minimize a sequence of adversarially generated convex loss functions. This procedure can be described as a $T$ round iterative game between the player and the adversary. In this paper, we present quantum algorithms for the problem and show for the first time that potential quantum advantages are possible for problems of online convex optimization. Specifically, our contributions are as follows. (i) When the player is allowed to query zeroth-order oracles $O(1)$ times in each round as feedback, we give a quantum algorithm that achieves $O(\sqrt{T})$ regret without additional dependence of the dimension $n$, which outperforms the already known optimal classical algorithm only achieving $O(\sqrt{nT})$ regret. Note that the regret of our quantum algorithm has achieved the lower bound of classical first-order methods. (ii) We show that for strongly convex loss functions, the quantum algorithm can achieve $O(\log T)$ regret with $O(1)$ queries as well, which means that the quantum algorithm can achieve the same regret bound as the classical algorithms in the full information setting.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantum Speedup and Limitations on Matroid Property Problems

This paper initiates the study of quantum algorithms for matroid property problems. It is shown that quadratic quantum speedup is possible for the calculation problem of finding the girth or the number of circuits (bases, flats, hyperplanes) of a matroid, and for the decision problem of deciding whether a matroid is uniform or Eulerian, by giving a uniform lower bound $Ω(\sqrt{\binom{n}{\lfloor n/2\rfloor}})$ on the query complexity for all these problems. On the other hand, for the uniform matroid decision problem, an asymptotically optimal quantum algorithm is proposed which achieves the lower bound, and for the girth problem, an almost optimal quantum algorithm is given with query complexity $O(\log n\sqrt{\binom{n}{\lfloor n/2\rfloor}})$. In addition, for the paving matroid decision problem, a lower bound $Ω(\sqrt{\binom{n}{\lfloor n/2\rfloor}/n})$ on the query complexity is obtained, and an $O(\sqrt{\binom{n}{\lfloor n/2\rfloor}})$ quantum algorithm is presented.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

High-performance parallel classical scheme for simulating shallow quantum circuits

Recently, constant-depth quantum circuits are proved more powerful than their classical counterparts at solving certain problems, e.g., the two-dimensional (2D) hidden linear function (HLF) problem regarding a symmetric binary matrix. To further investigate the boundary between classical and quantum computing models, in this work we propose a high-performance two-stage classical scheme to solve a full-sampling variant of the 2D HLF problem, which combines traditional classical parallel algorithms and a gate-based classical circuit model together for exactly simulating the target shallow quantum circuits. Under reasonable parameter assumptions, a theoretical analysis reveals our classical simulator consumes less runtime than that of near-term quantum processors for most problem instances. Furthermore, we demonstrate the typical all-connected 2D grid instances by moderate FPGA circuits, and show our designed parallel scheme is a practically scalable, high-efficient and operationally convenient tool for simulating and verifying graph-state circuits performed by current quantum hardware.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Quantum Architecture Search with Meta-learning

Variational quantum algorithms (VQAs) have been successfully applied to quantum approximate optimization algorithms, variational quantum compiling and quantum machine learning models. The performances of VQAs largely depend on the architecture of parameterized quantum circuits (PQCs). Quantum architecture search (QAS) aims to automate the design of PQCs in different VQAs with classical optimization algorithms. However, current QAS algorithms do not use prior experiences and search the quantum architecture from scratch for each new task, which is inefficient and time consuming. In this paper, we propose a meta quantum architecture search (MetaQAS) algorithm, which learns good initialization heuristics of the architecture (i.e., meta-architecture), along with the meta-parameters of quantum gates from a number of training tasks such that they can adapt to new tasks with a small number of gradient updates, which leads to fast learning on new tasks. The proposed MetaQAS can be used with arbitrary gradient-based QAS algorithms. Simulation results of variational quantum compiling on three- and four-qubit circuits show that the architectures optimized by MetaQAS converge much faster than a state-of-the-art gradient-based QAS algorithm, namely DQAS. MetaQAS also achieves a better solution than DQAS after fine-tuning of gate parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Characterization of exact one-query quantum algorithms

The quantum query models is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$ can be exactly computed by a one-query quantum algorithm if and only if $f(x)=x_{i_1}$ or ${x_{i_1} \oplus x_{i_2} }$ (up to isomorphism). Note that unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of $f$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quantum generative adversarial network for generating discrete distribution

Quantum machine learning has recently attracted much attention from the community of quantum computing. In this paper, we explore the ability of generative adversarial networks (GANs) based on quantum computing. More specifically, we propose a quantum GAN for generating classical discrete distribution, which has a classical-quantum hybrid architecture and is composed of a parameterized quantum circuit as the generator and a classical neural network as the discriminator. The parameterized quantum circuit only consists of simple one-qubit rotation gates and two-qubit controlled-phase gates that are available in current quantum devices. Our scheme has the following characteristics and potential advantages: (i) It is intrinsically capable of generating discrete data (e.g., text data), while classical GANs are clumsy for this task due to the vanishing gradient problem. (ii) Our scheme avoids the input/output bottlenecks embarrassing most of the existing quantum learning algorithms that either require to encode the classical input data into quantum states, or output a quantum state corresponding to the solution instead of giving the solution itself, which inevitably compromises the speedup of the quantum algorithm. (iii) The probability distribution implicitly given by data samples can be loaded into a quantum state, which may be useful for some further applications.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quantum speedup for twin support vector machines

We devise new quantum algorithms that exponentially speeds up the training and prediction procedures of twin support vector machines (TSVM). To train TSVMs using quantum methods, we demonstrate how to prepare the desired input states according to classical data, and these states are used in the quantum algorithm for the system of linear equations. In the prediction process, we employ a quantum circuit to estimate the distances from a new sample to the hyperplanes and then make a decision. The proposed quantum algorithms can learn two non-parallel hyperplanes and classify a new sample by comparing the distances from the sample to the two hyperplanes in $O(\log mn)$ time, where $m$ is the sample size and $n$ is the dimension of each data point. In contrast, the corresponding classical algorithm requires polynomial time for both the training and prediction procedures.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Security Improvements of Several Basic Quantum Private Query Protocols with O(log N) Communication Complexity

New quantum private database (with N elements) query protocols are presented and analyzed. Protocols preserve O(logN) 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 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(logN) communication complexity, at most half of the user privacy could leak to such a database in our protocol, while in the QPQ protocol, 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(\sqrt{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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lower bounds on the size of semi-quantum finite automata

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

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Promise problems solved by quantum and classical finite automata

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 $ε\leq 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 $ε\leq 1/3$; and especially, (3) there are promise problems $A(p)$ with prime $p$ that can be solved {\em 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties

In this paper, we study a model of quantum Markov chains that is a quantum analogue of Markov chains and is obtained by replacing probabilities in transition matrices with quantum operations. We show that this model is very suited to describe hybrid systems that consist of a quantum component and a classical one, although it has the same expressive power as another quantum Markov model proposed in the literature. Indeed, hybrid systems are often encountered in quantum information processing; for example, both quantum programs and quantum protocols can be regarded as hybrid systems. Thus, we further propose a model called hybrid quantum automata (HQA) that can be used to describe these hybrid systems that receive inputs (actions) from the outer world. We show the language equivalence problem of HQA is decidable in polynomial time. Furthermore, we apply this result to the trace equivalence problem of quantum Markov chains, and thus it is also decidable in polynomial time. Finally, we discuss model checking linear-time properties of quantum Markov chains, and show the quantitative analysis of regular safety properties can be addressed successfully.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On hybrid models of quantum finite automata

In the literature, there exist several quantum finite automata (QFA) models with both quantum and classical states. These models are of particular interest,as they show praiseworthy advantages over the fully quantum models in some nontrivial aspects. This paper characterizes these models in a uniform framework by proposing a general hybrid model consisting of a quantum component and a classical one which can interact with each other. The existing hybrid QFA can be naturally regarded as the general model with specific communication patterns (classical-quantum, quantum-classical, and two-way, respectively). We further clarify the relationship between these hybrid QFA and some other quantum models. In particular, it is shown that hybrid QFA can be simulated exactly by QFA with quantum operations, which in turn has a close relationship with two early proposed models: {\it ancialla QFA} and {\it quantum sequential machines}.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Decidability of minimization of fuzzy automata

State minimization is a fundamental problem in automata theory. The problem is also of great importance in the study of fuzzy automata. However, most work in the literature considered only state reduction of fuzzy automata, whereas the state minimization problem is almost untouched for fuzzy automata. Thus in this paper we focus on the latter problem. Formally, the decision version of the minimization problem of fuzzy automata is as follows: \begin{itemize} \item Given a fuzzy automaton $\mathcal{A}$ and a natural number $k$, that is, a pair $\langle \mathcal{A}, k\rangle$, is there a $k$-state fuzzy automaton equivalent to $\mathcal{A}$? \end{itemize} We prove for the first time that the above problem is decidable for fuzzy automata over totally ordered lattices. To this end, we first give the concept of systems of fuzzy polynomial equations and then present a procedure to solve these systems. Afterwards, we apply the solvability of a system of fuzzy polynomial equations to the minimization problem mentioned above, obtaining the decidability. Finally, we point out that the above problem is at least as hard as PSAPCE-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Exponentially more concise quantum recognition of non-RMM regular languages

We show that there are quantum devices that accept all regular languages and that are exponentially more concise than deterministic finite automata (DFA). For this purpose, we introduce a new computing model of {\it one-way quantum finite automata} (1QFA), namely, {\it one-way quantum finite automata together with classical states} (1QFAC), which extends naturally both measure-only 1QFA and DFA and whose state complexity is upper-bounded by both. The original contributions of the paper are the following. First, we show that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. Second, we prove that 1QFAC are at most exponentially more concise than DFA. Third, we show that the previous bound is tight for families of regular languages that are not recognized by measure-once (RMO), measure-many (RMM) and multi-letter 1QFA. % More concretely we exhibit regular languages $L^0(m)$ for $m$ prime such that: (i) $L^0(m)$ cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts $L^0(m)$ has $O(m)$ states; (iii) there is a 1QFAC with constant classical states and $O(\log(m))$ quantum basis that accepts $L^0(m)$. Fourth, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. Finally, we show that state minimization of 1QFAC is decidable within EXPSPACE. We conclude the paper by posing some open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

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

{\it Two-way quantum 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\in {\mathbb{Z}}^+$ and any $ε<1/2$, we show that: {enumerate} 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 $\varepsilon$) of quantum states and $\mathbf{O}(\log{\frac{1}ε)}$ classical states, whereas the sizes of the corresponding {\it deterministic finite automata} (DFA), {\it two-way nondeterministic finite automata} (2NFA) and polynomial expected running time {\it two-way probabilistic finite automata} (2PFA) are at least $2m+2$, $\sqrt{\log{m}}$, and $\sqrt[3]{(\log m)/b}$, respectively; there exists a language $L^{twin}(m)=\{wcw| w\in\{a,b\}^*\}$ 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 $\mathbf{O}(\log{\frac{1}ε)}$ classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least $2^m$, $\sqrt{m}$, and $\sqrt[3]{m/b}$, respectively; {enumerate} where $b$ is a constant.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

One-way finite automata with quantum and classical states

In this paper, we introduce and explore a new model of {\it quantum finite automata} (QFA). Namely, {\it one-way finite automata with quantum and classical states} (1QCFA), a one way version of {\it two-way finite automata with quantum and classical states} (2QCFA) introduced by Ambainis and Watrous in 2002 \cite{AJ}. First, we prove that {\it one-way probabilistic finite automata} (1PFA) \cite{AP} and {\it one-way quantum finite automata with control language} (1QFACL) \cite{ACB} as well as several other models of QFA, can be simulated by 1QCFA. Afterwards, we explore several closure properties for the family of languages accepted by 1QCFA. Finally, the state complexity of 1QCFA is explored and the main succinctness result is derived. Namely, for any prime $m$ and any $ε_1>0$, there exists a language $L_{m}$ that cannot be recognized by any {\it measure-many one-way quantum finite automata} (MM-1QFA) \cite{Kon97} with bounded error $7/9+ε_1$, and any 1PFA recognizing it has at last $m$ states, but $L_{m}$ can be recognized by a 1QCFA for any error bound $ε>0$ with $\bf{O}(\log{m})$ quantum states and 12 classical states.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States

{\it Two-way finite automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous, and it was shown that 2QCFA have superiority over {\it two-way probabilistic finite automata} (2PFA) for recognizing some non-regular languages such as the language $L_{eq}=\{a^{n}b^{n}\mid n\in \mathbf{N}\}$ and the palindrome language $L_{pal}=\{ω\in \{a,b\}^*\midω=ω^R\}$, where $x^R$ is $x$ in the reverse order. It is interesting to find more languages like these that witness the superiority of 2QCFA over 2PFA. In this paper, we consider the language $L_{m}=\{xcy\mid Σ=\{a, b, c\}, x,y\in\{a,b\}^{*},c\inΣ, |x|=|y|\}$ that is similar to the middle language $L_{middle}=\{xay\mid x,y\inΣ^{*},a\inΣ, |x|=|y|\}$. We prove that the language $L_{m}$ can be recognized by 2QCFA with one-sided error in polynomial expected time. Also, we show that $L_{m}$ can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus $L_{m}$ is another witness of the fact that 2QCFA are more powerful than their classical counterparts.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Two-tape finite automata with quantum and classical states

{\it Two-way finite automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous, and {\it two-way two-tape deterministic finite automata} (2TFA) were introduced by Rabin and Scott. In this paper we study 2TFA and propose a new computing model called {\it two-way two-tape finite automata with quantum and classical states} (2TQCFA). First, we give efficient 2TFA algorithms for recognizing languages which can be recognized by 2QCFA. Second, we give efficient 2TQCFA algorithms to recognize several languages whose status vis-a-vis 2QCFA have been posed as open questions, such as $L_{square}=\{a^{n}b^{n^{2}}\mid n\in \mathbf{N}\}$. Third, we show that $\{a^{n}b^{n^{k}}\mid n\in \mathbf{N}\}$ can be recognized by {\it $(k+1)$-tape deterministic finite automata} ($(k+1)$TFA). Finally, we introduce {\it $k$-tape automata with quantum and classical states} ($k$TQCFA) and prove that $\{a^{n}b^{n^{k}}\mid n\in \mathbf{N}\}$ can be recognized by $k$TQCFA.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Characterizations of one-way general quantum finite automata

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), and measure-many one-way general quantum finite automata (MM-1gQFA). We prove that MO-1gQFA recognize, with bounded error, precisely the set of all 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, which is greatly different from the conventional case in which the number of times the measurement is performed in the computation generally affects the language recognition power of one-way QFA. Finally, we present a sufficient and necessary condition for two MM-1gQFA to be equivalent.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Decidability of the Equivalence of Multi-Letter Quantum Finite Automata

Multi-letter {\it quantum finite automata} (QFAs) were a quantum variant of classical {\it one-way multi-head finite automata} (J. Hromkovič, Acta Informatica 19 (1983) 377-384), and it has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages $(a+b)^{*}b$ that are unacceptable by the previous one-way QFAs. In this paper, we study the decidability of the equivalence of multi-letter QFAs, and the main technical contributions are as follows: (1) We show that any two automata, a $k_{1}$-letter QFA ${\cal A}_1$ and a $k_{2}$-letter QFA ${\cal A}_2$, over the same input alphabet $Σ$ are equivalent if and only if they are $(n^2m^{k-1}-m^{k-1}+k)$-equivalent, where $m=|Σ|$ is the cardinality of $Σ$, $k=\max(k_{1},k_{2})$, and $n=n_{1}+n_{2}$, with $n_{1}$ and $n_{2}$ being the numbers of states of ${\cal A}_{1}$ and ${\cal A}_{2}$, respectively. When $k=1$, we obtain the decidability of equivalence of measure-once QFAs in the literature. It is worth mentioning that our technical method is essentially different from that for the decidability of the case of single input alphabet (i.e., $m=1$). (2) However, if we determine the equivalence of multi-letter QFAs by checking all strings of length not more than $ n^2m^{k-1}-m^{k-1}+k$, then the worst time complexity is exponential, i.e., $O(n^6m^{n^2m^{k-1}-m^{k-1}+2k-1})$. Therefore, we design a polynomial-time $O(m^{2k-1}n^{8}+km^kn^{6})$ algorithm for determining the equivalence of any two multi-letter QFAs. Here, the time complexity is concerning the number of states in the multi-letter QFAs, and $k$ is thought of as a constant.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Local Entanglement Is Not Necessary for Perfect Discrimination between Unitary Operations Acting on Two-Qudits by LOCC

Recently, the problem of discriminating multipartite unitary operations by local operations and classical communication (LOCC) has attracted significant attention. The latest work in the literature on this problem showed that two multipartite unitary operations can always be perfectly distinguished by LOCC when a finite number of runs are allowable. However, in these schemes, local entanglement (an entangled state holden by one party) was required, which seems to imply that local entanglement is necessary for perfect discrimination between unitary operations by LOCC. In this article, we show that a perfect discrimination between two unitary operations acting on a two-qudits can always be achieved without exploiting any entanglement. As a result, we conclude that local entanglement is not necessary for perfect discrimination between unitary operations acting on two-qudits by LOCC.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Optimal discrimination between quantum operations

In this paper, we address the problem of discriminating two given quantum operations. Firstly, based on the Bloch representation of single qubit systems, we give the exact minimum error probability of discriminating two single qubit quantum operations by unentangled input states. In particular, for the Pauli channels discussed in [Phys. Rev. A {\bf 71}, 062340 (2005)], we use a more intuitional and visual method to deal with their discrimination problem. Secondly, we consider the condition for perfect discrimination of two quantum operations. Specially, we get that two generalized Pauli channels are perfectly distinguishable if and only if their characteristic vectors are orthogonal.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

A Polynomial-Time Algorithm for the Equivalence between Quantum Sequential Machines

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 (Theoretical Computer Science 358 (2006) 65-74). However, using this result to check the equivalence likely needs exponential expected time. In this paper, 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 (Theoretical Computer Science 237 (2000) 275-306). (3) We give that two MO-1QFAs with n_1 and n_2 states, respectively, are equivalent iff they are (n_1+n_2)^2--equivalent, and further obtain a polynomial-time algorithm for deciding the equivalence between two MO-1QFAs. (4) We provide a counterexample showing that Koshiba's method to solve the problem of deciding the equivalence between MM-1QFAs may be not valid, and thus the problem is left open again.

0 citations0 reviewsNo code linkedOpen access