Search

Rank-varying computational complexity describes those computations in which the complexity of executing each step is not a constant, but evolves throughout the computation as a function of the order of execution of each step [2]. This paper identifies practical instances of this computational paradigm in the procedures for computing the quantum Fourier transform and its inverse. It is shown herein that under the constraints imposed by quantum decoherence, only a parallel approach can guarantee a reliable solution or, alternatively, improve scalability. [ABSTRACT FROM AUTHOR]

We develop an entanglement verification method not based on Bell inequalities, that achieves a higher reliability per number of qubits tested than existing procedures of this kind. Used in a quantum cryptographic context, the method gives rise to a new protocol for distributing classical keys through insecure quantum channels. The cost of quantum and classical communication is significantly reduced in the new protocol, while its security is increased with respect to other entanglement-based protocols exchanging the same number of qubits. To achieve this performance, our scheme relies on a simple quantum circuit and the ability to store qubits. [ABSTRACT FROM AUTHOR]

It has been said that quantum cryptography in general offers a secure solution to the problem of key enhancement. This means that two parties who already share a small secret key, can use quantum protocols to establish a new large secret key. This large secret key can be arbitrarily long and is unbreakable. Thus, to date, the main contribution of quantum cryptography has been believed to be quantum key enhancement. This paper shows that quantum cryptography can do significantly more. The quantum protocol described here distributes an unbreakable secret key to the two parties by relying on public information only. This is the first time that quantum cryptography is shown to be able to produce secret information using only public information. This contribution is also unique for cryptography in general, classical and quantum. [ABSTRACT FROM AUTHOR]

Determining the optimal location of a switching center in a tree network of users is accurately modeled by the median problem. A real-time approach is used in this paper to investigate the dynamics of such a communication network in two cases: (1) a growing tree of nodes associated with equal demand rates, and (2) a stream of corrections that arbitrarily change the demand rates at the nodes. The worst-case analysis performed in both situations clearly demonstrates the importance of parallelism in such real-time paradigms. It is shown that the error generated by the best sequential algorithm in the first case can be arbitrarily large. A synergistic behavior is revealed when the quality-up is investigated in the second case. [ABSTRACT FROM AUTHOR]

This paper is structured around the idea that a finite Universal Computer cannot be realized and presents in detail a series of unconventional computing paradigms supporting this idea from a quantum mechanical perspective. [ABSTRACT FROM AUTHOR]

The authors reflect on the selected researched materials from the workshop on Unconventional Computational Problems held on August 13, 2007 in Kingston, Ontario. The authors briefly state that unconventional computation is committed to discovering new computing ideas that can solve problems that are difficult for ordinary computers. The authors add that the discussions from the researched materials will provide the reader insights about the theory of computing.