Relevant bibliographies by topics / Quantum halting problem

Academic literature on the topic 'Quantum halting problem'

Author: Grafiati
Published: 10 December 2022
Last updated: 29 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Quantum halting problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Quantum halting problem"

1

SHALYT-MARGOLIN, A. E., V. I. STRAZHEV, and A. YA. TREGUBOVICH. "IRREVERSIBILITY IN THE HALTING PROBLEM OF QUANTUM COMPUTER." Modern Physics Letters B 21, no. 16 (July 10, 2007): 977–80. http://dx.doi.org/10.1142/s0217984907013559.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Dietrich, Eric, and Chris Fields. "Equivalence of the Frame and Halting Problems." Algorithms 13, no. 7 (July 20, 2020): 175. http://dx.doi.org/10.3390/a13070175.

Full text
Abstract:
The open-domain Frame Problem is the problem of determining what features of an open task environment need to be updated following an action. Here we prove that the open-domain Frame Problem is equivalent to the Halting Problem and is therefore undecidable. We discuss two other open-domain problems closely related to the Frame Problem, the system identification problem and the symbol-grounding problem, and show that they are similarly undecidable. We then reformulate the Frame Problem as a quantum decision problem, and show that it is undecidable by any finite quantum computer.
APA, Harvard, Vancouver, ISO, and other styles
3

Song, Daegene. "Unsolvability of the Halting Problem in Quantum Dynamics." International Journal of Theoretical Physics 47, no. 7 (December 6, 2007): 1785–91. http://dx.doi.org/10.1007/s10773-007-9621-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Siomau, Michael. "Undecidable, Unrecognizable, and Quantum Computing." Quantum Reports 2, no. 3 (July 1, 2020): 337–42. http://dx.doi.org/10.3390/quantum2030023.

Full text
Abstract:
Quantum computing allows us to solve some problems much faster than existing classical algorithms. Yet, the quantum computer has been believed to be no more powerful than the most general computing model—the Turing machine. Undecidable problems, such as the halting problem, and unrecognizable inputs, such as the real numbers, are beyond the theoretical limit of the Turing machine. I suggest a model for a quantum computer, which is less general than the Turing machine, but may solve the halting problem for any task programmable on it. Moreover, inputs unrecognizable by the Turing machine can be recognized by the model, thus breaking the theoretical limit for a computational task. A quantum computer is not just a successful design of the Turing machine as it is widely perceived now, but is a different, less general but more powerful model for computing, the practical realization of which may need different strategies than those in use now.
APA, Harvard, Vancouver, ISO, and other styles
5

Tarrataca, Luís, and Andreas Wichert. "Quantum Iterative Deepening with an Application to the Halting Problem." PLoS ONE 8, no. 3 (March 8, 2013): e57309. http://dx.doi.org/10.1371/journal.pone.0057309.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

MANIN, YURI I. "Renormalisation and computation II: time cut-off and the Halting Problem." Mathematical Structures in Computer Science 22, no. 5 (September 6, 2012): 729–51. http://dx.doi.org/10.1017/s0960129511000508.

Full text
Abstract:
This is the second instalment in the project initiated in Manin (2012). In the first Part, we argued that both the philosophy and technique of perturbative renormalisation in quantum field theory could be meaningfully transplanted to the theory of computation, and sketched several contexts supporting this view.In this second part, we address some of the issues raised in Manin (2012) and develop them further in three contexts: a categorification of the algorithmic computations; time cut-off and anytime algorithms; and, finally, a Hopf algebra renormalisation of the Halting Problem.
APA, Harvard, Vancouver, ISO, and other styles
7

Proos, J., and Ch Zalka. "Shor's discrete logarithm quantum algorithm for elliptic curves." Quantum Information and Computation 3, no. 4 (July 2003): 317–44. http://dx.doi.org/10.26421/qic3.4-3.

Full text
Abstract:
We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits. In this paper we only consider elliptic curves over GF(p) and not yet the equally important ones over GF(2^n) or other finite fields. The main technical difficulty is to implement Euclid's gcd algorithm to compute multiplicative inverses modulo p. As the runtime of Euclid's algorithm depends on the input, one difficulty encountered is the ``quantum halting problem''.
APA, Harvard, Vancouver, ISO, and other styles
8

GÖKDEN, BURÇ. "SEMICLASSICAL QUANTUM COMPUTATION SOLUTIONS TO THE COUNT TO INFINITY PROBLEM: A BRIEF DISCUSSION." International Journal of Quantum Information 03, no. 01 (March 2005): 159–64. http://dx.doi.org/10.1142/s0219749905000645.

Full text
Abstract:
In this paper we briefly define distance vector routing algorithms, their advantages and possible drawbacks. On these possible drawbacks, currently widely used methods split horizon and poisoned reverse are defined and compared. The count to infinity problem is specified and classified to be a halting problem, and a proposition stating that entangled states used in quantum computation can be used to handle this problem is examined. Several solutions to this problem by using entangled states are proposed and a very brief introduction to entangled states is presented.
APA, Harvard, Vancouver, ISO, and other styles
9

Ji, Zhengfeng, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. "MIP* = RE." Communications of the ACM 64, no. 11 (November 2021): 131–38. http://dx.doi.org/10.1145/3485628.

Full text
Abstract:
Note from the Research Highlights Co-Chairs: A Research Highlights paper appearing in Communications is usually peer-reviewed prior to publication. The following paper is unusual in that it is still under review. However, the result has generated enormous excitement in the research community, and came strongly nominated by SIGACT, a nomination seconded by external reviewers. The complexity class NP characterizes the collection of computational problems that have efficiently verifiable solutions. With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of randomness (the class MA), interaction (the class IP), and the possibility to interact with multiple proofs, or provers (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols. In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement. We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomial-time verifier interacting with two all-powerful but noncommunicating provers sharing entanglement. The result resolves long-standing open problems in the foundations of quantum mechanics (Tsirelson's problem) and operator algebras (Connes' embedding problem).
APA, Harvard, Vancouver, ISO, and other styles
10

Shojaei-Fard, Ali. "Non-perturbative graph languages, halting problem and complexity." Forum Mathematicum, June 30, 2022. http://dx.doi.org/10.1515/forum-2021-0119.

Full text
Abstract:
Abstract We explain the foundations of a new class of formal languages for the construction of large Feynman diagrams which contribute to solutions of all combinatorial Dyson–Schwinger equations in a given strongly coupled gauge field theory. Then we build a new Hopf algebraic structure on non-perturbative production rules which leads us to formulate the halting problem for the corresponding replacing–gluing graph grammars in our formal graph languages on the basis of Manin’s renormalization Hopf algebra. In addition, we apply topology of graphons to associate a complexity parameter to this new class of graph grammars. At the final step, we address some applications of our new formal language platform to Quantum Field Theory. The first application concerns the constructive role of non-perturbative graph languages in dealing with quantum gauge symmetries in the context of the Hopf ideals generated by Slavnov–Taylor or Ward–Takahashi identities. The second application concerns the importance of the complexities of non-perturbative replacing–gluing graph grammars in formulating a new generalization of the circuit complexity on the space of Dyson–Schwinger equations. We provide a geometric interpretation of non-perturbative circuit complexities. The third application concerns the impact of non-perturbative replacing–gluing graph grammars in providing some new tools for the computation of the Kolmogorov complexity of Dyson–Schwinger equations.
APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Quantum halting problem"

1

Lagana, Antonio. "Quantum computation and a universal quantum computer." Thesis, 2012. http://hdl.handle.net/2440/77320.

Full text
Abstract:
This thesis covers two main topics in quantum computing: universal quantum computation and quantum search. We first demonstrate how a quantum harmonic oscillator can be used to implement the universal set of quantum gates and thereby serve as one possible building block for a universal quantum computer. We then address the core and primary focus of this thesis, the theoretical construction of a machine that can compute every computable function, that is, a universal (i.e.programmable) quantum computer. We thereby settle the questions that have been raised over the years regarding the validity of the UQTM proposed by Deutsch in 1985. We then demonstrate how to interface the universal quantum computer to external quantum devices by developing programs that implement well-known oracle based algorithms, including the well-known Grover search algorithm, using networked quantum oracle devices. Finally, we develop a partial search oracle and explore symmetry based partial search algorithms utilizing this oracle.
Thesis (Ph.D.) -- University of Adelaide, School of Chemistry and Physics, 2012
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography