It was shown in [KW97] that the class of languages recognized by 1-way QFAs is a proper subset of regular languages.
If we wish to find out whether a QFA recognizes the given language, the answer depends on the accepting probability of the QFA. It was proved in [AF98] that if the QFA is to give the correct answer with a large probability (greater than 7/9), then the same language can be recognized with probability 1. However, some of such languages can be recognized by QFA with a probability 0.68... However, 7/9 is greater than 0.68... Now we have found the precise value of the crucial threshold. It is $\frac{52 + 4\sqrt 7}{81}$.
In [AF98] a property of deterministic finite automata was found such that if the minimal automaton for a regular language has this property, then the language cannot be recognized with a probability higher than the crucial probability above. [BP99] generalized this property to show that if for various input words this property can happen unlimited number of times, then the regular language cannot be recognized by a QFA with any probability exceeding 1/2.
Maris Valdats proved that the construction in [BP99] is not the only obstacle for a language to be recognized by a QFA. This way he proved that there are regular languages L1 and L2 such that they are recognizable by QFA with a probability exceeding 1/2 but their intersection is not recognizable by a QFA with any probability exceeding 1/2.
References:[AF98] Andris Ambainis and Rusins Freivalds, ``1--way quantum finite automata: their strengths, weaknesses and generalizations'', in: Proc. 39th FOCS, 1998, pp. 332--341. See also http://xxx.lanl.gov/arXiv/quant-ph/9904066.
[BP99] Alex Brodsky and Nicholas Pippenger, ``Characterizations of 1--Way Quantum Finite Automata'', http://xxx.lanl.gov/arXiv/quant-ph/9903014.
[KW97] Attila Kondacs and John Watrous, ``On the power of quantum finite state automata'', in: Proc. 38th FOCS, 1997, pp. 66--75.
We extend algorithmic information theory to quantum mechanics. Due to difficulties and ambiguities in finding an appropriate notion of description complexity for quantum states, we take the construction of a universal semicomputable density matrix (``apriori probability'') as a starting point, and define complexity as its negative logarithm.
A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain, but new questions arise due to non-commutativity.
We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by Vitanyi (we show that the latter is sometimes as large as n-2log n) and the qubit complexity defined by Berthiaume, Dam and Laplante.
When sending classical information through a quantum channel we search for the optimal output state. In the talk the necessity and sufficiency of Kuhn-Tucker conditions for optimality will be demonstrated. Some related inequalities will be discussed.
Basing on the general expressions for the random coding and expurgation bounds for the reliability function of classical-quantum channel with continuous alphabet and constrained inputs, we compute several important information quantities for a general quantum Gaussian channel, such as: the Gallager functions, the cutoff rate and margins for the reliability function at zero rate. This reqires some new formulas for quantum Gaussian states, namely the quantum Fourier transform of arbitrary positive degree of a Gaussian density operator and the fidelity between two Gaussian states.
It is well known that for some computational tasks (such as integer factorisation) quantum processes can offer an exponential speedup in time over any known classical computational method. We will consider the question: what is the physical origin of the extra power of quantum computation? We show that for quantum computations on pure states an exponential benefit can be obtained only if there is increasing multi-partite entanglement with increasing input size. Computations with mixed states are more complicated and it seems possible that exponential benefits might be exhibited by processes operating with only separable mixed states. However recent work of Popescu, Linden and Braunstein has shown that the special case -- of implementing the known quantum algorithms with so-called pseudo-pure states (e.g. as in liquid state NMR quantum computing) -- cannot exhibit an exponential benefit in physical resources over classical computation, if the states remain separable throughout the computation. Finally we will make some remarks on the comparison of quantum computation with classical analogue computation.