Квантовият компютър: квантовите ординали и типовете алгоритмична неразрешимост

Васил Пенчев

Published Jan 1, 2005• 0 citations

Abstract

A definition of quantum computer is supposed: as a countable set of Turing machines on the ground of: quantum parallelism, reversibility, entanglement. Qubit is the set of all the i–th binary location cells transforming in parallel by unitary matrices. The Church thesis is suggested in the form relevat to quantum computer. The notion of the non–finite (but not infinite) potency of a set is introduced .

Related papers

Отвъд машината на Тюринг: квантовият компютър

Vasil Penchev

Quantum computer is considered as a generalization of Turing machine. The bits are substituted by qubits. In turn, a "qubit" is the generalization of "bit" referring to infinite sets or series. It extends the consept of calculation from finite processes and algorithms to infinite ones, impossible as to any Turing machines (such as our computers). However, the concept of quantum computer mets all paradoxes of infinity such as Gödel's incompletness theorems (1931), etc. A philosophical reflection on how quantum computer might implement the idea of "infinite calculation" is the main subject.

Jan 1, 20140 citations

Quantum computation: From Church-Turing thesis to Qubits

Shankhadip Kundu, Rajdeep Kundu, Shubhabrata Kundu +4 more

In the paper we interpret the Church Turing thesis of Computation Algorithm and how it differs from the strong Church Turing thesis in the field of computation. Church Turing thesis can be classified as Strong Church Turing thesis and Normal Church Turing thesis. Church Turing hypothesis says “that a computing problem can be solved in any computer if and only if it can be solved on a very simple ‘machine’, named TURING MACHINE”. We introspect the difference in the model of computers that are developed on these two competitive algorithms. We will also be studying the physical realization of bits in a quantum computer with special mention to the commercial quantum computer systems offered at the moment. Our objective is to find out the relation of a quantum bit and the Strong Church Turing Thesis converging the gap between theoretical model and physical structure.

IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)Oct 1, 20167 citations

Quantum computing and quantum complexity theory

Umesh V. Vazirani

There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].

IEEE International Symposium on Circuits and Systems proceedingsJan 1, 20000 citations

On capabilities of quantum-mechanical computer models

Svetomir Simonović

The work includes the analyses of the theoretical capabilities of quantum-mechanical versus classical computer models in terms of their universality, their application domain, their efficacy in solving the problems and their technological feasibility. The concepts of deterministic Turing machine, probabilistic Turing machine and quantum-mechanical Turing machine are exposed. The concept of basic information unit of quantum-mechanical computer modelqubit is introduced and the qubit is represented through the use of Bloch sphere. The use of Dirac's bra-ket notation in description of quantum-mechanical state is explained, and the notation is used to form state equation of a quantummechanical Turing machine cell. Especially, consequences of quantum parallelism, quantum interference and wave function collapse are studied in respect to capabilities of quantum-mechanical computer models. The interrelationship between classes of problems that can be efficiently solved by quantum mechanical and/or classical computer models is displayed.

TehnikaJan 1, 20221 citation

A Quantum Computer in a “Chinese Room”

Vasil Dinev Penchev

Pattern recognition is represented as the limit, to which an infinite Turing processconverges. A Turing machine, in which the bits are substituted with qubits, is introduced. Thatquantum Turing machine can recognize two complementary patterns in any data. That ability ofuniversal pattern recognition is interpreted as an intellect featuring any quantum computer. Theproperty is valid only within a quantum computer: To utilize it, the observer should be sited insideit. Being outside it, the observer would obtain quite different result depending on the degreeof the entanglement of the quantum computer and observer. All extraordinary properties ofa quantum computer are due to involving a converging infinite computational process contentingnecessarily both a continuous advancing calculation and a leap to the limit. Three types ofquantum computation can be distinguished according to whether the series is a finite one, an infiniterational or irrational number.

May 4, 20200 citations

Quantum Computer: Quantum Model and Reality

Vasil Dinev Penchev

Any computer can create a model of reality. The hypothesis that quantum computer can generate such a model designated as quantum, which coincides with the modeled reality, is discussed. Its reasons are the theorems about the absence of “hidden variables” in quantum mechanics. The quantum modeling requires the axiom of choice. The following conclusions are deduced from the hypothesis. A quantum model unlike a classical model can coincide with reality. Reality can be interpreted as a quantum computer. The physical processes represent computations of the quantum computer. Quantum information is the real fundament of the world. The conception of quantum computer unifies physics and mathematics and thus the material and the ideal world. Quantum computer is a non-Turing machine in principle. Any quantum computing can be interpreted as an infinite classical computational process of a Turing machine. Quantum computer introduces the notion of “actually infinite computational process”. The discussed hypothesis is consistent with all quantum mechanics. The conclusions address a form of neo-Pythagoreanism: Unifying the mathematical and physical, quantum computer is situated in an intermediate domain of their mutual transformation.

Jan 1, 20200 citations