Quantum information, cognition, and music
Identifieur interne : 000023 ( Pmc/Curation ); précédent : 000022; suivant : 000024Quantum information, cognition, and music
Auteurs : Maria L. Dalla Chiara [Italie] ; Roberto Giuntini [Italie] ; Roberto Leporini [Italie] ; Eleonora Negri [Italie] ; Giuseppe Sergioli [Italie]Source :
- Frontiers in Psychology ; 2015.
Abstract
Parallelism represents an essential aspect of human mind/brain activities. One can recognize some common features between psychological parallelism and the characteristic parallel structures that arise in quantum theory and in quantum computation. The article is devoted to a discussion of the following questions:
a comparison between classical probabilistic Turing machines and quantum Turing machines. possible applications of the quantum computational semantics to cognitive problems. parallelism in music.
Url:
DOI: 10.3389/fpsyg.2015.01583
PubMed: 26539139
PubMed Central: 4612715
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000023
Links to Exploration step
PMC:4612715Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Quantum information, cognition, and music</title><author><name sortKey="Dalla Chiara, Maria L" sort="Dalla Chiara, Maria L" uniqKey="Dalla Chiara M" first="Maria L." last="Dalla Chiara">Maria L. Dalla Chiara</name><affiliation wicri:level="1"><nlm:aff id="aff1"><institution>Dipartimento di Lettere e Filosofia, Università di Firenze</institution><country>Firenze, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author><author><name sortKey="Giuntini, Roberto" sort="Giuntini, Roberto" uniqKey="Giuntini R" first="Roberto" last="Giuntini">Roberto Giuntini</name><affiliation wicri:level="1"><nlm:aff id="aff2"><institution>Dipartimento di Pedagogia, Psicologia, Filosofia, Università di Cagliari</institution><country>Cagliari, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author><author><name sortKey="Leporini, Roberto" sort="Leporini, Roberto" uniqKey="Leporini R" first="Roberto" last="Leporini">Roberto Leporini</name><affiliation wicri:level="1"><nlm:aff id="aff3"><institution>Dipartimento di Ingegneria Gestionale, dell'Informazione e della Produzione, Università di Bergamo</institution><country>Dalmine, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author><author><name sortKey="Negri, Eleonora" sort="Negri, Eleonora" uniqKey="Negri E" first="Eleonora" last="Negri">Eleonora Negri</name><affiliation wicri:level="1"><nlm:aff id="aff4"><institution>Scuola di Musica di Fiesole, San Domenico di Fiesole</institution><country>Fiesole, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author><author><name sortKey="Sergioli, Giuseppe" sort="Sergioli, Giuseppe" uniqKey="Sergioli G" first="Giuseppe" last="Sergioli">Giuseppe Sergioli</name><affiliation wicri:level="1"><nlm:aff id="aff2"><institution>Dipartimento di Pedagogia, Psicologia, Filosofia, Università di Cagliari</institution><country>Cagliari, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">26539139</idno><idno type="pmc">4612715</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4612715</idno><idno type="RBID">PMC:4612715</idno><idno type="doi">10.3389/fpsyg.2015.01583</idno><date when="2015">2015</date><idno type="wicri:Area/Pmc/Corpus">000023</idno><idno type="wicri:Area/Pmc/Curation">000023</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Quantum information, cognition, and music</title><author><name sortKey="Dalla Chiara, Maria L" sort="Dalla Chiara, Maria L" uniqKey="Dalla Chiara M" first="Maria L." last="Dalla Chiara">Maria L. Dalla Chiara</name><affiliation wicri:level="1"><nlm:aff id="aff1"><institution>Dipartimento di Lettere e Filosofia, Università di Firenze</institution><country>Firenze, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author><author><name sortKey="Giuntini, Roberto" sort="Giuntini, Roberto" uniqKey="Giuntini R" first="Roberto" last="Giuntini">Roberto Giuntini</name><affiliation wicri:level="1"><nlm:aff id="aff2"><institution>Dipartimento di Pedagogia, Psicologia, Filosofia, Università di Cagliari</institution><country>Cagliari, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author><author><name sortKey="Leporini, Roberto" sort="Leporini, Roberto" uniqKey="Leporini R" first="Roberto" last="Leporini">Roberto Leporini</name><affiliation wicri:level="1"><nlm:aff id="aff3"><institution>Dipartimento di Ingegneria Gestionale, dell'Informazione e della Produzione, Università di Bergamo</institution><country>Dalmine, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author><author><name sortKey="Negri, Eleonora" sort="Negri, Eleonora" uniqKey="Negri E" first="Eleonora" last="Negri">Eleonora Negri</name><affiliation wicri:level="1"><nlm:aff id="aff4"><institution>Scuola di Musica di Fiesole, San Domenico di Fiesole</institution><country>Fiesole, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author><author><name sortKey="Sergioli, Giuseppe" sort="Sergioli, Giuseppe" uniqKey="Sergioli G" first="Giuseppe" last="Sergioli">Giuseppe Sergioli</name><affiliation wicri:level="1"><nlm:aff id="aff2"><institution>Dipartimento di Pedagogia, Psicologia, Filosofia, Università di Cagliari</institution><country>Cagliari, Italy</country></nlm:aff><country xml:lang="fr">Italie</country><wicri:regionArea></wicri:regionArea><wicri:regionArea># see nlm:aff region in country</wicri:regionArea></affiliation></author></analytic><series><title level="j">Frontiers in Psychology</title><idno type="e-ISSN">1664-1078</idno><imprint><date when="2015">2015</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><p>Parallelism represents an essential aspect of human mind/brain activities. One can recognize some common features between psychological parallelism and the characteristic parallel structures that arise in quantum theory and in quantum computation. The article is devoted to a discussion of the following questions:
<list list-type="order"><list-item><p>a comparison between classical probabilistic Turing machines and quantum Turing machines.</p></list-item><list-item><p>possible applications of the quantum computational semantics to cognitive problems.</p></list-item><list-item><p>parallelism in music.</p></list-item></list></p></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Aerts, D" uniqKey="Aerts D">D. Aerts</name></author><author><name sortKey="Gabora, L" uniqKey="Gabora L">L. Gabora</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Aerts, D" uniqKey="Aerts D">D. Aerts</name></author><author><name sortKey="Gabora, L" uniqKey="Gabora L">L. Gabora</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Aerts, D" uniqKey="Aerts D">D. Aerts</name></author><author><name sortKey="Sozzo, S" uniqKey="Sozzo S">S. Sozzo</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Boncinelli, E" uniqKey="Boncinelli E">E. Boncinelli</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Budden, J" uniqKey="Budden J">J. Budden</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Dalla Chiara, M L" uniqKey="Dalla Chiara M">M. L. Dalla Chiara</name></author><author><name sortKey="Giuntini, R" uniqKey="Giuntini R">R. Giuntini</name></author><author><name sortKey="Ledda, A" uniqKey="Ledda A">A. Ledda</name></author><author><name sortKey="Leporini, R" uniqKey="Leporini R">R. Leporini</name></author><author><name sortKey="Sergioli, G" uniqKey="Sergioli G">G. Sergioli</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Dalla Chiara, M L" uniqKey="Dalla Chiara M">M. L. Dalla Chiara</name></author><author><name sortKey="Giuntini, R" uniqKey="Giuntini R">R. Giuntini</name></author><author><name sortKey="Leporini, R" uniqKey="Leporini R">R. Leporini</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Dalla Chiara, M L" uniqKey="Dalla Chiara M">M. L. Dalla Chiara</name></author><author><name sortKey="Giuntini, R" uniqKey="Giuntini R">R. Giuntini</name></author><author><name sortKey="Leporini, R" uniqKey="Leporini R">R. Leporini</name></author><author><name sortKey="Sergioli, G" uniqKey="Sergioli G">G. Sergioli</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Dalla Chiara, M L" uniqKey="Dalla Chiara M">M. L. Dalla Chiara</name></author><author><name sortKey="Giuntini, R" uniqKey="Giuntini R">R. Giuntini</name></author><author><name sortKey="Luciani, A R" uniqKey="Luciani A">A. R. Luciani</name></author><author><name sortKey="Negri, E" uniqKey="Negri E">E. Negri</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Damasio, A R" uniqKey="Damasio A">A. R. Damasio</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Fouche, W" uniqKey="Fouche W">W. Fouché</name></author><author><name sortKey="Heidema, J" uniqKey="Heidema J">J. Heidema</name></author><author><name sortKey="Jones, G" uniqKey="Jones G">G. Jones</name></author><author><name sortKey="Potgieter, P H" uniqKey="Potgieter P">P. H. Potgieter</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Gudder, S" uniqKey="Gudder S">S. Gudder</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Nielsen, M A" uniqKey="Nielsen M">M. A. Nielsen</name></author><author><name sortKey="Chuang, I L" uniqKey="Chuang I">I. L. Chuang</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Penrose, R" uniqKey="Penrose R">R. Penrose</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Principe, Q" uniqKey="Principe Q">Q. Principe</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Reichenbach, H" uniqKey="Reichenbach H">H. Reichenbach</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Savage, J E" uniqKey="Savage J">J. E. Savage</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Solomon, M" uniqKey="Solomon M">M. Solomon</name></author></analytic></biblStruct></listBibl></div1></back></TEI><pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">Front Psychol</journal-id><journal-id journal-id-type="iso-abbrev">Front Psychol</journal-id><journal-id journal-id-type="publisher-id">Front. Psychol.</journal-id><journal-title-group><journal-title>Frontiers in Psychology</journal-title></journal-title-group><issn pub-type="epub">1664-1078</issn><publisher><publisher-name>Frontiers Medeia S.A.</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="pmid">26539139</article-id><article-id pub-id-type="pmc">4612715</article-id><article-id pub-id-type="doi">10.3389/fpsyg.2015.01583</article-id><article-categories><subj-group subj-group-type="heading"><subject>Psychology</subject><subj-group><subject>Original Research</subject></subj-group></subj-group></article-categories><title-group><article-title>Quantum information, cognition, and music</article-title></title-group><contrib-group><contrib contrib-type="author"><name><surname>Dalla Chiara</surname><given-names>Maria L.</given-names></name><xref ref-type="aff" rid="aff1"><sup>1</sup></xref><xref ref-type="author-notes" rid="fn001"><sup>*</sup></xref><uri xlink:type="simple" xlink:href="http://loop.frontiersin.org/people/141606/overview"></uri></contrib><contrib contrib-type="author"><name><surname>Giuntini</surname><given-names>Roberto</given-names></name><xref ref-type="aff" rid="aff2"><sup>2</sup></xref></contrib><contrib contrib-type="author"><name><surname>Leporini</surname><given-names>Roberto</given-names></name><xref ref-type="aff" rid="aff3"><sup>3</sup></xref><uri xlink:type="simple" xlink:href="http://loop.frontiersin.org/people/261109/overview"></uri></contrib><contrib contrib-type="author"><name><surname>Negri</surname><given-names>Eleonora</given-names></name><xref ref-type="aff" rid="aff4"><sup>4</sup></xref></contrib><contrib contrib-type="author"><name><surname>Sergioli</surname><given-names>Giuseppe</given-names></name><xref ref-type="aff" rid="aff2"><sup>2</sup></xref></contrib></contrib-group><aff id="aff1"><sup>1</sup><institution>Dipartimento di Lettere e Filosofia, Università di Firenze</institution><country>Firenze, Italy</country></aff><aff id="aff2"><sup>2</sup><institution>Dipartimento di Pedagogia, Psicologia, Filosofia, Università di Cagliari</institution><country>Cagliari, Italy</country></aff><aff id="aff3"><sup>3</sup><institution>Dipartimento di Ingegneria Gestionale, dell'Informazione e della Produzione, Università di Bergamo</institution><country>Dalmine, Italy</country></aff><aff id="aff4"><sup>4</sup><institution>Scuola di Musica di Fiesole, San Domenico di Fiesole</institution><country>Fiesole, Italy</country></aff><author-notes><fn fn-type="edited-by"><p>Edited by: Sandro Sozzo, University of Leicester, UK</p></fn><fn fn-type="edited-by"><p>Reviewed by: Tomas Veloz, University of British Columbia, Canada; Matías Graffigna, University of Buenos Aires, Argentina</p></fn><corresp id="fn001">*Correspondence: Maria L. Dalla Chiara <email xlink:type="simple">dallachiara@unifi.it</email></corresp><fn fn-type="other" id="fn002"><p>This article was submitted to Cognition, a section of the journal Frontiers in Psychology</p></fn></author-notes><pub-date pub-type="epub"><day>21</day><month>10</month><year>2015</year></pub-date><pub-date pub-type="collection"><year>2015</year></pub-date><volume>6</volume><elocation-id>1583</elocation-id><history><date date-type="received"><day>08</day><month>8</month><year>2015</year></date><date date-type="accepted"><day>29</day><month>9</month><year>2015</year></date></history><permissions><copyright-statement>Copyright © 2015 Dalla Chiara, Giuntini, Leporini, Negri and Sergioli.</copyright-statement><copyright-year>2015</copyright-year><copyright-holder>Dalla Chiara, Giuntini, Leporini, Negri and Sergioli</copyright-holder><license xlink:href="http://creativecommons.org/licenses/by/4.0/"><license-p>This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY). The use, distribution or reproduction in other forums is permitted, provided the original author(s) or licensor are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms.</license-p></license></permissions><abstract><p>Parallelism represents an essential aspect of human mind/brain activities. One can recognize some common features between psychological parallelism and the characteristic parallel structures that arise in quantum theory and in quantum computation. The article is devoted to a discussion of the following questions:
<list list-type="order"><list-item><p>a comparison between classical probabilistic Turing machines and quantum Turing machines.</p></list-item><list-item><p>possible applications of the quantum computational semantics to cognitive problems.</p></list-item><list-item><p>parallelism in music.</p></list-item></list></p></abstract><kwd-group><kwd>Turing machines</kwd><kwd>quantum computation</kwd><kwd>quantum information</kwd><kwd>semantics</kwd><kwd>music cognition</kwd></kwd-group><funding-group><award-group><funding-source id="cn001">Italian Ministry of Scientific Research<named-content content-type="fundref-id">10.13039/501100003407</named-content></funding-source><award-id rid="cn001">L.R. 7 del 7 agosto 2007</award-id></award-group></funding-group><counts><fig-count count="9"></fig-count><table-count count="0"></table-count><equation-count count="44"></equation-count><ref-count count="18"></ref-count><page-count count="13"></page-count><word-count count="8477"></word-count></counts></article-meta></front><body><sec id="s1"><title>1. Introduction</title><p>Parallelism represents an essential aspect of the activities of human brain and mind. One can recognize some common features between psychological parallelism and the characteristic parallel structures that arise in quantum theory and in quantum computation, being responsible for the extraordinary efficiency and speed of quantum computers.</p><p>Quantum parallelism and classical parallelism are deeply different, although it is sometimes claimed that quantum Turing machines are nothing but special examples of classical probabilistic Turing machines<xref ref-type="fn" rid="fn0001"><sup>1</sup></xref>. But what exactly are quantum Turing machines? So far, the literature has not provided a rigorous “institutional” concept of <italic>quantum Turing machine</italic>. Some definitions seem to be based on a kind of “imitation” of the classical definition of <italic>Turing machine</italic>, by referring to a <italic>tape</italic> (where the symbols are written) and to a <italic>moving head</italic> (which changes its position on the tape)<xref ref-type="fn" rid="fn0002"><sup>2</sup></xref>. These concepts, however, seem to be hardly applicable to physical quantum computers. Both in the classical and in the quantum case, it is expedient to consider a more abstract concept: the notion of <italic>state machine</italic>, which neglects both tapes and moving heads. Every finite computational task realized in different computational models proposed in the literature can be simulated by a state machine<xref ref-type="fn" rid="fn0003"><sup>3</sup></xref>. In order to compare classical and quantum parallelism, we will analyze the concepts of (classical) <italic>deterministic state machine</italic>, (classical) <italic>probabilistic state machine</italic>, and <italic>quantum state machine</italic>. On this basis we will discuss the question: to what extent can quantum state machines be simulated by probabilistic state machines? (Sections 2, 3).</p><p>In the investigation about possible links between <italic>quantum structures</italic> and <italic>psychological structures</italic> a useful tool is represented by a special form of quantum logical semantics (called <italic>quantum computational semantics</italic>) that has been inspired by the theory of quantum computation. We will see how this semantics can be naturally applied to a formal analysis of musical compositions, where <italic>parallel structures, ambiguity, holism</italic>, and <italic>contextuality</italic> play an essential role (Sections 4, 5)<xref ref-type="fn" rid="fn0004"><sup>4</sup></xref>.</p><p>Our analysis seems to confirm a general conjecture that has been defended and discussed in different research-fields: the basic concepts of the quantum-theoretic formalism (which had for a long time been regarded as mysterious and potentially paradoxical) seem to have a <italic>universal</italic> interest that goes beyond the domain of microphysical phenomena.</p></sec><sec id="s2"><title>2. Classical deterministic and probabilistic machines</title><p>We will first introduce a formal definition for the notion of <italic>deterministic state machine</italic>. On this basis, <italic>probabilistic state machines</italic> will be represented as stochastic variants of deterministic machines, which are able to calculate different outputs with different probability-values.</p><p><bold>Definition 1</bold>. <italic>Deterministic state machine</italic>.</p><p>A <italic>deterministic state machine</italic> is an abstract system <bold>M</bold> based on the following elements:
<list list-type="order"><list-item><p>A finite set <inline-formula><mml:math id="M1"><mml:mi mathvariant="-tex-caligraphic">S</mml:mi></mml:math></inline-formula> of <italic>internal states</italic>, which contains an <italic>initial state s</italic><sub><italic>in</italic></sub> and includes a set of <italic>halting states</italic><inline-formula><mml:math id="M2"><mml:mi mathvariant="-tex-caligraphic">S</mml:mi></mml:math></inline-formula><sub><italic>halt</italic></sub> = {<italic>s</italic><sub><italic>halt</italic><sub><italic>j</italic></sub></sub> | <italic>j</italic> ∈ <italic>J</italic>}.</p></list-item><list-item><p>A finite alphabet, which can be identified with the set {0, 1} of the two classical bits. Any <italic>register</italic> represented by a bit-sequence <italic>w</italic> = (<italic>x</italic><sub>1</sub>, …, <italic>x</italic><sub><italic>n</italic></sub>) is a <italic>word</italic> (of length <italic>n</italic>). Any pair (<italic>s, w</italic>) consisting of an internal state <italic>s</italic> and of a word <italic>w</italic> represents a possible <italic>configuration</italic> of <bold>M</bold>, which is interpreted as follows: <bold>M</bold> is in the internal state <italic>s</italic> and <italic>w</italic> is the word written on an ideal tape.</p></list-item><list-item><p>A set of words that represent possible <italic>word-inputs</italic> for <bold>M</bold>.</p></list-item><list-item><p>A <italic>program</italic>, which is identified with a finite sequence of <italic>rules</italic>:
<disp-formula id="E1"><mml:math id="M3"><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mi>t</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:math></disp-formula></p><p>Each <italic>R</italic><sub><italic>i</italic></sub> is a partial function that transforms configurations into configurations. We may have: <italic>R</italic><sub><italic>i</italic></sub> = <italic>R</italic><sub><italic>j</italic></sub> with <italic>i</italic> ≠ <italic>j</italic>. The number <italic>i</italic>, corresponding to the rule <italic>R</italic><sub><italic>i</italic></sub>, represents the <italic>i</italic>-th step of the program. The following conditions are required:
<list list-type="simple"><list-item><p>4.1 The rule <italic>R</italic><sub>0</sub> is defined for any configuration (<italic>s</italic><sub>0</sub>, <italic>w</italic><sub>0</sub>), where <italic>s</italic><sub>0</sub> is the initial state <italic>s</italic><sub><italic>in</italic></sub> and <italic>w</italic><sub>0</sub> is a possible word-input. We have:
<disp-formula id="E2"><mml:math id="M4"><mml:msub><mml:mi>R</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>:</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>w</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>↦</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>w</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:math></disp-formula></p><p>where <italic>s</italic><sub>1</sub> is different from the initial state and from all halting states (if <italic>t</italic> ≠ 0).</p></list-item><list-item><p>4.2 For any <italic>i</italic> (0 < <italic>i</italic> < <italic>t</italic>),
<disp-formula id="E3"><mml:math id="M5"><mml:msub><mml:mi>R</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>:</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>w</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>↦</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mtext> </mml:mtext><mml:mo>+</mml:mo><mml:mtext> </mml:mtext><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>w</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mtext> </mml:mtext><mml:mo>+</mml:mo><mml:mtext> </mml:mtext><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:math></disp-formula></p><p>where <italic>s</italic><sub><italic>i</italic> + 1</sub> is different from all <italic>s</italic><sub><italic>i</italic></sub>, …, <italic>s</italic><sub>0</sub> and from all halting states.</p></list-item><list-item><p>4.3 <italic>R</italic><sub><italic>t</italic></sub>: (<italic>s</italic><sub><italic>t</italic></sub>, <italic>w</italic><sub><italic>t</italic></sub>) ↦ (<italic>s</italic><sub><italic>t</italic> + 1</sub>, <italic>w</italic><sub><italic>t</italic> + 1</sub>),</p><p>where <italic>s</italic><sub><italic>t</italic> + 1</sub> is a halting state.</p><p>Each configuration (<italic>s</italic><sub><italic>i</italic> + 1</sub>, <italic>w</italic><sub><italic>i</italic> + 1</sub>) represents the <italic>output</italic> for the step <italic>i</italic> and the <italic>input</italic> for the step <italic>i</italic> + 1.</p></list-item></list></p></list-item></list></p><p>The concept of <italic>computation</italic> of a deterministic state machine can be now defined as follows.</p><p><bold>Definition 2</bold>. <italic>Computation of a deterministic state machine</italic>.</p><p>A <italic>computation</italic> of a deterministic state machine <bold>M</bold> is a finite sequence of configurations
<disp-formula id="E4"><mml:math id="M6"><mml:mo stretchy="false">(</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>w</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mtext> </mml:mtext><mml:mo>+</mml:mo><mml:mtext> </mml:mtext><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>w</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mtext> </mml:mtext><mml:mo>+</mml:mo><mml:mtext> </mml:mtext><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:math></disp-formula></p><p>where:
<list list-type="order"><list-item><p><italic>w</italic><sub>0</sub> is a possible word-input of <bold>M</bold>.</p></list-item><list-item><p><italic>s</italic><sub>0</sub>, …, <italic>s</italic><sub><italic>t</italic> + 1</sub> are different internal states of <bold>M</bold> such that: <italic>s</italic><sub>0</sub> = <italic>s</italic><sub><italic>in</italic></sub> and <italic>s</italic><sub><italic>t</italic> + 1</sub> is a halting state.</p></list-item><list-item><p>For any <italic>i</italic> (0 ≤ <italic>i</italic> ≤ <italic>t</italic>),
<disp-formula id="E5"><mml:math id="M7"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mtext> </mml:mtext><mml:msub><mml:mi>w</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mtext> </mml:mtext><mml:mo>=</mml:mo><mml:mtext> </mml:mtext><mml:msub><mml:mi>R</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:mtext> </mml:mtext><mml:msub><mml:mi>w</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where <italic>R</italic><sub><italic>i</italic></sub> is the <italic>i</italic>-th rule of the program.</p></list-item></list></p><p>The configurations (<italic>s</italic><sub>0</sub>, <italic>w</italic><sub>0</sub>) and (<italic>s</italic><sub><italic>t</italic> + 1</sub>, <italic>w</italic><sub><italic>t</italic> + 1</sub>) represent, respectively, the <italic>input</italic> and the <italic>output</italic> of the computation; while the words <italic>w</italic><sub>0</sub> and <italic>w</italic><sub><italic>t</italic> + 1</sub> represent, respectively, the <italic>word-input</italic> and the <italic>word-output</italic> of the computation.</p><p>Apparently, each deterministic state machine is devoted to a single task that is determined by its program.</p><p>Let us now turn to the concept of <italic>probabilistic state machine</italic>. The only difference between deterministic and probabilistic state machines concerns the program, which may be stochastic in the case of a probabilistic state machine (<bold>PM</bold>). In such a case, instead of a sequence of rules, we will have a sequence (<italic>Seq</italic><sub>0</sub>, …, <italic>Seq</italic><sub><italic>t</italic></sub>) of sequences of rules such that:
<disp-formula id="E6"><mml:math id="M8"><mml:mtable columnalign="left"><mml:mtr><mml:mtd><mml:mi>S</mml:mi><mml:mi>e</mml:mi><mml:msub><mml:mi>q</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mi>r</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mtext> </mml:mtext><mml:mo>…</mml:mo><mml:mo>…</mml:mo><mml:mo>…</mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>S</mml:mi><mml:mi>e</mml:mi><mml:msub><mml:mi>q</mml:mi><mml:mi>t</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mi>t</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mi>t</mml:mi><mml:mi>l</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:mtd></mml:mtr></mml:mtable></mml:math></disp-formula></p><p>Each rule <italic>R<sub>i<sub>j</sub></sub></italic> (occurring in the sequence <italic>Seq</italic><sub><italic>i</italic></sub>) is associated to a probability-value <italic>p<sub>i<sub>j</sub></sub></italic> such that:
<disp-formula id="E7"><mml:math id="M9"><mml:mstyle displaystyle="true"><mml:munder><mml:mo>∑</mml:mo><mml:mi>j</mml:mi></mml:munder><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:msub></mml:mrow></mml:mstyle><mml:mo>=</mml:mo><mml:mn>1.</mml:mn></mml:math></disp-formula></p><p>From an intuitive point of view, <italic>p<sub>i<sub>j</sub></sub></italic> represents the probability that the rule <italic>R<sub>i<sub>j</sub></sub></italic> be applied at the <italic>i</italic>-th step. A deterministic state machine is, of course, a special case of a probabilistic state machine characterized by the following property: each sequence <italic>Seq</italic><sub><italic>i</italic></sub> consists of a single rule <italic>R</italic><sub><italic>i</italic></sub>.</p><p>Any probabilistic state machine naturally gives rise to a graph-structure for any choice of an input-configuration <italic>conf</italic><sub>0</sub> = (<italic>s</italic><sub>0</sub>, <italic>w</italic><sub>0</sub>). As an example, consider the following simple case: a probabilistic state machine <bold>PM</bold> whose program consists of two sequences, each consisting of two rules:
<disp-formula id="E8"><mml:math id="M10"><mml:mtable columnalign="left"><mml:mtr><mml:mtd><mml:mi>S</mml:mi><mml:mi>e</mml:mi><mml:msub><mml:mi>q</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>S</mml:mi><mml:mi>e</mml:mi><mml:msub><mml:mi>q</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mn>1</mml:mn><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mn>1</mml:mn><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:mtd></mml:mtr></mml:mtable></mml:math></disp-formula></p><p>The graph associated to <bold>PM</bold> for the configuration <italic>conf</italic><sub>0</sub> is illustrated by Figure <xref ref-type="fig" rid="F1">1</xref>.</p><fig id="F1" position="float"><label>Figure 1</label><caption><p><bold>The graph of PM</bold>.</p></caption><graphic xlink:href="fpsyg-06-01583-g0001"></graphic></fig><p>How do probabilistic machines compute? In order to define the concept of <italic>computation</italic> of a probabilistic machine, let us first introduce the notions of <italic>program-path</italic> and of <italic>computation-path</italic> of a given probabilistic machine.</p><p><bold>Definition 3</bold>. <italic>Program-path and computation-path</italic>.</p><p>Let <bold>PM</bold> be a probabilistic state machine with program (<italic>Seq</italic><sub>0</sub>, …, <italic>Seq</italic><sub><italic>t</italic></sub>).</p><list list-type="bullet"><list-item><p>A <italic>program-path</italic> of <bold>PM</bold> is a sequence
<disp-formula id="E36"><mml:math id="M11"><mml:mrow><mml:mi mathvariant="-tex-caligraphic">P</mml:mi><mml:mtext> </mml:mtext><mml:mo>=</mml:mo><mml:mtext> </mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mi>h</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mi>t</mml:mi><mml:mi>k</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>consisting of <italic>t</italic> rules, where each <italic>R<sub>i<sub>j</sub></sub></italic> is a rule from <italic>Seq</italic><sub><italic>i</italic></sub> (probabilistically independent of all other rules of <inline-formula><mml:math id="M12"><mml:mi mathvariant="-tex-caligraphic">P</mml:mi></mml:math></inline-formula>).</p></list-item><list-item><p>For any choice of an input (<italic>s</italic><sub>0</sub>, <italic>w</italic><sub>0</sub>), any program-path <inline-formula><mml:math id="M13"><mml:mi mathvariant="-tex-caligraphic">P</mml:mi></mml:math></inline-formula> determines a sequence of configurations
<disp-formula id="E9"><mml:math id="M14"><mml:mrow><mml:mi mathvariant="-tex-caligraphic">CP</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>w</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>w</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mtext> </mml:mtext><mml:mo>+</mml:mo><mml:mtext> </mml:mtext><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>w</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mtext> </mml:mtext><mml:mo>+</mml:mo><mml:mtext> </mml:mtext><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where (<italic>s</italic><sub><italic>i</italic> + 1</sub>, <italic>w</italic><sub><italic>i</italic> + 1</sub>) = <italic>R<sub>i<sub>j</sub></sub></italic>(<italic>s</italic><sub><italic>i</italic></sub>, <italic>w</italic><sub><italic>i</italic></sub>) and <italic>R<sub>i<sub>j</sub></sub></italic> is the <italic>i</italic>-th element of <inline-formula><mml:math id="M15"><mml:mi mathvariant="-tex-caligraphic">P</mml:mi></mml:math></inline-formula>. This sequence is called the <italic>computation-path</italic> of <bold>PM</bold> determined by the program-path <inline-formula><mml:math id="M16"><mml:mi mathvariant="-tex-caligraphic">P</mml:mi></mml:math></inline-formula> and by the input (<italic>s</italic><sub>0</sub>, <italic>w</italic><sub>0</sub>). The configuration (<italic>s</italic><sub><italic>t</italic> + 1</sub>, <italic>w</italic><sub><italic>t</italic> + 1</sub>) represents the output of <inline-formula><mml:math id="M17"><mml:mi mathvariant="-tex-caligraphic">C</mml:mi></mml:math></inline-formula><inline-formula><mml:math id="M18"><mml:mi mathvariant="-tex-caligraphic">P</mml:mi></mml:math></inline-formula>.</p></list-item></list><p>Any program-path <inline-formula><mml:math id="M19"><mml:mi mathvariant="-tex-caligraphic">P</mml:mi></mml:math></inline-formula> = (<italic>R</italic><sub>0<sub><italic>h</italic></sub></sub>, …, <italic>R<sub>i<sub>j</sub></sub></italic>, …, <italic>R<sub>t<sub>k</sub></sub></italic>) has a well-determined probability-value <italic>p</italic>(<inline-formula><mml:math id="M20"><mml:mi mathvariant="-tex-caligraphic">P</mml:mi></mml:math></inline-formula>), which is defined as follows (in terms of the probability-values of its rules):
<disp-formula id="E10"><mml:math id="M21"><mml:mi>p</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi mathvariant="-tex-caligraphic">P</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>:</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mi>h</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>·</mml:mo><mml:mo>…</mml:mo><mml:mo>·</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>·</mml:mo><mml:mo>…</mml:mo><mml:mo>·</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mrow><mml:msub><mml:mi>t</mml:mi><mml:mi>k</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>.</mml:mo></mml:math></disp-formula></p><p>As expected, the probability-value of a program-path <inline-formula><mml:math id="M22"><mml:mi mathvariant="-tex-caligraphic">P</mml:mi></mml:math></inline-formula> naturally determines the probability-values of all corresponding computation-paths. It is sufficient to put:
<disp-formula id="E11"><mml:math id="M23"><mml:mi>p</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi mathvariant="-tex-caligraphic">CP</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>:</mml:mo><mml:mo>=</mml:mo><mml:mi>p</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi mathvariant="-tex-caligraphic">P</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:math></disp-formula></p><p>Consider now the set <bold>P</bold><sub><bold>PM</bold></sub> of all program-paths and the set <bold>CP</bold><sub><bold>PM</bold></sub> of all computation-paths of a probabilistic machine <bold>PM</bold>. One can easily show that:
<disp-formula id="E12"><mml:math id="M24"><mml:mrow><mml:mstyle displaystyle="true"><mml:munder><mml:mo>∑</mml:mo><mml:mi>i</mml:mi></mml:munder><mml:mrow><mml:mo stretchy="false">{</mml:mo><mml:mi>p</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi mathvariant="-tex-caligraphic">P</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>|</mml:mo><mml:msub><mml:mi mathvariant="-tex-caligraphic">P</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>∈</mml:mo><mml:msub><mml:mstyle mathvariant="bold" mathsize="normal"><mml:mi>P</mml:mi></mml:mstyle><mml:mrow><mml:mstyle mathvariant="bold" mathsize="normal"><mml:mi>P</mml:mi><mml:mi>M</mml:mi></mml:mstyle></mml:mrow></mml:msub></mml:mrow></mml:mstyle><mml:mo stretchy="false">}</mml:mo><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:munder><mml:mo>∑</mml:mo><mml:mi>i</mml:mi></mml:munder><mml:mrow><mml:mo stretchy="false">{</mml:mo><mml:mi>p</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi mathvariant="-tex-caligraphic">C</mml:mi><mml:msub><mml:mi mathvariant="-tex-caligraphic">P</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>|</mml:mo><mml:mi mathvariant="-tex-caligraphic">C</mml:mi><mml:msub><mml:mi mathvariant="-tex-caligraphic">P</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>∈</mml:mo><mml:mstyle mathvariant="bold" mathsize="normal"><mml:mi>C</mml:mi></mml:mstyle><mml:msub><mml:mstyle mathvariant="bold" mathsize="normal"><mml:mi>P</mml:mi></mml:mstyle><mml:mrow><mml:mstyle mathvariant="bold" mathsize="normal"><mml:mi>P</mml:mi><mml:mi>M</mml:mi></mml:mstyle></mml:mrow></mml:msub><mml:mo stretchy="false">}</mml:mo><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mstyle><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>On this basis the concept of <italic>computation</italic> of a probabilistic state machine can be defined as follows.</p><p><bold>Definition 4</bold>. <italic>Computation of a probabilistic state machine</italic>.</p><p>A <italic>computation</italic> of a probabilistic state machine <bold>PM</bold> with input (<italic>s</italic><sub>0</sub>, <italic>w</italic><sub>0</sub>) is the system of all computation-paths of <bold>PM</bold> with input (<italic>s</italic><sub>0</sub>, <italic>w</italic><sub>0</sub>).</p><p>Unlike the case of deterministic state machines, a computation of a probabilistic state machine does not yield a unique output. For any choice of a configuration-input (<italic>s</italic><sub>0</sub>, <italic>w</italic><sub>0</sub>), the computation-output is a system of possible configuration-outputs <inline-formula><mml:math id="M25"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:msubsup><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>t</mml:mi><mml:mo> + </mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msubsup><mml:mo>,</mml:mo><mml:msubsup><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mi>t</mml:mi><mml:mo> + </mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msubsup></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></inline-formula>, where each <inline-formula><mml:math id="M26"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:msubsup><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>t</mml:mi><mml:mo> + </mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msubsup><mml:mo>,</mml:mo><mml:msubsup><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mi>t</mml:mi><mml:mo> + </mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msubsup></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></inline-formula> corresponds to a computation-path <inline-formula><mml:math id="M27"><mml:mi mathvariant="-tex-caligraphic">C</mml:mi></mml:math></inline-formula><inline-formula><mml:math id="M28"><mml:mi mathvariant="-tex-caligraphic">P</mml:mi></mml:math></inline-formula><sub><italic>i</italic></sub>. As expected, each <inline-formula><mml:math id="M29"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:msubsup><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>t</mml:mi><mml:mo> + </mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msubsup><mml:mo>,</mml:mo><mml:msubsup><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mi>t</mml:mi><mml:mo> + </mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msubsup></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></inline-formula> has a well-determined probability-value that is defined as follows:
<disp-formula id="E13"><mml:math id="M30"><mml:mtable columnalign="left"><mml:mtr><mml:mtd><mml:mi>p</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msubsup><mml:mi>s</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>i</mml:mi></mml:msubsup><mml:mo>,</mml:mo><mml:msubsup><mml:mi>w</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>i</mml:mi></mml:msubsup><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>:</mml:mo><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:munder><mml:mo>∑</mml:mo><mml:mi>i</mml:mi></mml:munder><mml:mrow><mml:mrow><mml:mo>{</mml:mo><mml:mrow><mml:mi>p</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi mathvariant="-tex-caligraphic">C</mml:mi><mml:msub><mml:mi mathvariant="-tex-caligraphic">P</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>|</mml:mo><mml:mtext>the configuration-output of</mml:mtext></mml:mrow></mml:mrow></mml:mrow></mml:mstyle></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mtext> </mml:mtext><mml:mrow><mml:mrow><mml:mi mathvariant="-tex-caligraphic">C</mml:mi><mml:msub><mml:mi mathvariant="-tex-caligraphic">P</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mtext> is </mml:mtext><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:msubsup><mml:mi>s</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>i</mml:mi></mml:msubsup><mml:mo>,</mml:mo><mml:msubsup><mml:mi>w</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>i</mml:mi></mml:msubsup></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mo>}</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mtd></mml:mtr></mml:mtable></mml:math></disp-formula></p><p>One can easily show that the sum of the probability-values of all configuration-outputs of any machine <bold>PM</bold> is 1.</p></sec><sec id="s3"><title>3. Quantum state machines</title><p>The strong parallelism that characterizes quantum computers is based on two quantum-theoretic notions that have been often described as mysterious and potentially paradoxical: <italic>superposition</italic> and <italic>entanglement</italic>. For the readers who are not expert of quantum theory it is expedient to recall some concepts of the quantum formalism that are used in quantum computation<xref ref-type="fn" rid="fn0005"><sup>5</sup></xref>. The basic idea is that any <italic>piece of quantum information</italic> is mathematically represented as a possible <italic>state</italic> of a quantum system that can store and transmit the information in question. In the simplest situations one is dealing with a single particle <italic>S</italic> (say, an electron or a photon), whose “mathematical environment” is a special example of a vector space: the two-dimensional Hilbert space ℂ<sup>2</sup>, based on the set of all ordered pairs of complex numbers. The canonical (orthonormal) basis of ℂ<sup>2</sup> consists of the two following unit-vectors:
<disp-formula id="E14"><mml:math id="M31"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mn>0</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>0</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>;</mml:mo><mml:mtext> </mml:mtext><mml:mrow><mml:mo>|</mml:mo><mml:mn>1</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>which represent, in this framework, the two classical bits (0 and 1), or (equivalently) the two classical truth-values (<italic>Falsity</italic> and <italic>Truth</italic>). A <italic>pure state</italic> corresponds to a <italic>maximal piece of information</italic> that cannot be consistently extended to a richer knowledge. Such state is represented as a unit-vector |ψ〉 that can be expressed as a <italic>superposition</italic> of the two elements of the canonical basis of ℂ<sup>2</sup>:
<disp-formula id="E15"><mml:math id="M32"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mi>ψ</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:msub><mml:mi>c</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mrow><mml:mo>|</mml:mo><mml:mn>0</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>+</mml:mo><mml:msub><mml:mi>c</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mrow><mml:mo>|</mml:mo><mml:mn>1</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where <italic>c</italic><sub>0</sub> and <italic>c</italic><sub>1</sub> (also called <italic>amplitudes</italic>) are complex numbers such that <inline-formula><mml:math id="M33"><mml:mo>|</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mn>0</mml:mn></mml:mrow></mml:msub><mml:msup><mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo> + </mml:mo><mml:mo>|</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:msup><mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:math></inline-formula>.</p><p>The physical interpretation of |ψ〉 (also called <italic>qubit-state</italic> or, briefly, <italic>qubit</italic>) is the following: the physical system <italic>S</italic> in state |ψ〉 might satisfy the physical properties that are <italic>certain</italic> for the bit |0〉 with probability <inline-formula><mml:math id="M34"><mml:mo>|</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mn>0</mml:mn></mml:mrow></mml:msub><mml:msup><mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:math></inline-formula> and might satisfy the physical properties that are <italic>certain</italic> for the bit |1〉 with probability <inline-formula><mml:math id="M35"><mml:mo>|</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:msup><mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:math></inline-formula>. Due to the characteristic indeterminism of quantum theory, the pure state |ψ〉 is at the same time a <italic>maximal and logically incomplete piece of information</italic> that cannot <italic>decide</italic> some important physical properties of the system <italic>S</italic>. Accordingly, from an intuitive point of view, one can say that |ψ〉 describes a kind of <italic>cloud of potential properties</italic> that might become <italic>actual</italic> when a measurement is performed. Measuring a physical quantity (by means of an apparatus associated to the canonical basis) determines a sudden transformation of the qubit |ψ〉 either into the bit |0〉 or into the bit |1〉. Such transformation is usually called <italic>collapse of the wave-function</italic>.</p><p>Not all states associated to a physical system <italic>S</italic> are pure. Non-maximal pieces of information can be represented as <italic>mixtures of pure states</italic> (special examples of operators called <italic>density operators</italic>). In the space ℂ<sup>2</sup> a density operator ρ can be represented as a convenient finite sum of projection-operators:
<disp-formula id="E16"><mml:math id="M36"><mml:mrow><mml:mi>ρ</mml:mi><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:munder><mml:mo>∑</mml:mo><mml:mi>i</mml:mi></mml:munder><mml:mrow><mml:msub><mml:mi>w</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:mstyle><mml:msub><mml:mi>P</mml:mi><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>ψ</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow></mml:mrow></mml:msub><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where <italic>w</italic><sub><italic>i</italic></sub> are real numbers such that <inline-formula><mml:math id="M37"><mml:munder class="msub"><mml:mrow><mml:mo>∑</mml:mo></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:munder><mml:msub><mml:mrow><mml:mi>w</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:math></inline-formula>, while each <italic>P</italic><sub>|<sub>ψ</sub><sub><italic>i</italic></sub>〉</sub> is a projection-operator that projects along the direction of |ψ〉. Notice that such representation is not generally unique. A density operator that cannot be represented as a projection <italic>P</italic><sub>|ψ〉</sub> is called a <italic>proper mixture</italic>. While pure states codify an essential indetermination of some relevant properties of the quantum system under investigation, mixtures may correspond to an <italic>epistemic uncertainty</italic> of the observer. Unlike pure states (which always satisfy some well-determined properties), there are mixtures that cannot decide any (non-trivial) property of the associated system. An example of this kind is the state <inline-formula><mml:math id="M38"><mml:mi>ρ</mml:mi><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac><mml:mstyle class="text"><mml:mtext class="texttt" mathvariant="monospace">I</mml:mtext></mml:mstyle></mml:math></inline-formula>, where <monospace>I</monospace> is the identity operator of the space ℂ<sup>2</sup>.</p><p>As happens in classical information theory, quantum computation also needs complex pieces of information, which are supposed to be stored by composite quantum systems (generally consisting of <italic>n</italic> subsystems). Accordingly, one can naturally adopt the quantum-theoretic formalism for the mathematical representation of composite physical systems, based on the use of <italic>tensor products</italic> (special examples of products)<xref ref-type="fn" rid="fn0006"><sup>6</sup></xref>. While a single qubit is a unit-vector of the space ℂ<sup>2</sup>, a pure state representing a complex piece of information can be identified with a unit-vector of the <italic>n</italic>-fold tensor product of ℂ<sup>2</sup>:
<disp-formula id="E17"><mml:math id="M39"><mml:mrow><mml:msup><mml:mo>⊗</mml:mo><mml:mi>n</mml:mi></mml:msup><mml:msup><mml:mi>ℂ</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>=</mml:mo><mml:munder><mml:munder><mml:mrow><mml:msup><mml:mi>ℂ</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>⊗</mml:mo><mml:mo>…</mml:mo><mml:mo>⊗</mml:mo><mml:msup><mml:mi>ℂ</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow><mml:mo stretchy="true">︸</mml:mo></mml:munder><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>t</mml:mi><mml:mi>i</mml:mi><mml:mi>m</mml:mi><mml:mi>e</mml:mi><mml:mi>s</mml:mi></mml:mrow></mml:munder><mml:mo stretchy="false">(</mml:mo><mml:mtext>with </mml:mtext><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Such vectors are called <italic>quregisters</italic>. The canonical basis of the space ⊗<sup><italic>n</italic></sup>ℂ<sup>2</sup> consists af all <italic>registers</italic>, products of bits that have the following form:
<disp-formula id="E18"><mml:math id="M40"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>x</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>⊗</mml:mo><mml:mo>…</mml:mo><mml:mo>⊗</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>x</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mtext> (where any </mml:mtext><mml:msub><mml:mi>x</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mtext> is either </mml:mtext><mml:mn>0</mml:mn><mml:mtext> or </mml:mtext><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Instead of |<italic>x</italic><sub>1</sub>〉 ⊗ … ⊗ |<italic>x</italic><sub><italic>n</italic></sub>〉, it is customary to write |<italic>x</italic><sub>1</sub>, …, <italic>x</italic><sub><italic>n</italic></sub>〉. Any quregister can be represented as a superposition of registers:
<disp-formula id="E19"><mml:math id="M41"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mi>ψ</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:munder><mml:mo>∑</mml:mo><mml:mi>i</mml:mi></mml:munder><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:mstyle><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where <italic>c</italic><sub><italic>i</italic></sub> are complex numbers such that <inline-formula><mml:math id="M42"><mml:munder class="msub"><mml:mrow><mml:mo>∑</mml:mo></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:munder><mml:mo>|</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msub><mml:msup><mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>.</mml:mo></mml:math></inline-formula></p><p>A tensor product |ψ<sub>1</sub>〉 ⊗ … ⊗ |ψ<sub><italic>n</italic></sub>〉 (of <italic>n</italic> quregisters) is often briefly indicated by: |ψ<sub>1</sub>〉…|ψ<sub><italic>n</italic></sub>〉.</p><p>Quantum computation makes essential use of some characteristic quantum states that are called <italic>entangled</italic>. In order to illustrate the concept of entanglement from an intuitive point of view, let us refer to a simple paradigmatic case. We are concerned with a composite physical system <italic>S</italic> consisting of two subsystems <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> (say, a two-electron system). By the quantum-theoretic rules that concern the mathematical description of composite systems, all states of <italic>S</italic> shall live in the tensor product <inline-formula><mml:math id="M43"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula> = <inline-formula><mml:math id="M44"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> ⊗ <inline-formula><mml:math id="M45"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub>, where <inline-formula><mml:math id="M46"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> and <inline-formula><mml:math id="M47"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub> are the Hilbert spaces associated to the systems <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub>, respectively. The observer has a <italic>maximal information</italic> about <italic>S</italic>: a <italic>pure state</italic> |ψ〉 of <inline-formula><mml:math id="M48"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula>. What can be said about the states of the two subsystems? Due to the form of |ψ〉, such states cannot be pure: they are represented by two identical <italic>mixtures</italic>, which codify a “maximal degree of uncertainty.” A typical possible form of |ψ〉 is the following <italic>Bell-state</italic>:
<disp-formula id="E20"><mml:math id="M49"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mi>ψ</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>+</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>which lives in the space ℂ<sup>2</sup> ⊗ ℂ<sup>2</sup>, whose canonical basis consists of the four vectors |0, 0〉, |0, 1〉, |1, 0〉, |1, 1〉.</p><p>This gives rise to the following physical interpretation: the global system <italic>S</italic> might satisfy the properties that are <italic>certain</italic> either for the state |0, 0〉 or for the state |1, 1〉 with probability-value <inline-formula><mml:math id="M50"><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:math></inline-formula>. At the same time, |ψ〉 determines that the <italic>reduced state</italic> of both subsystems (<italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub>) is the mixture <inline-formula><mml:math id="M51"><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac><mml:mstyle class="text"><mml:mtext class="texttt" mathvariant="monospace">I</mml:mtext></mml:mstyle></mml:math></inline-formula>. Although it is not determined whether the state of the global system <italic>S</italic> is |0, 0〉 or |1, 1〉, the two subsystems <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> can be described as “entangled,” because in both possible cases they would satisfy the same properties, turning out to be <italic>indistinguishable</italic>. As a consequence, any measurement performed by an observer either on system <italic>S</italic><sub>1</sub> or on system <italic>S</italic><sub>2</sub> would instantaneously transform the <italic>potential</italic> properties of both subsystems into <italic>actual</italic> properties (by <italic>collapse of the wave-function</italic>).</p><p>The celebrated “Einstein–Podolsky–Rosen paradox”(<italic>EPR</italic>) is based on a similar physical situation. As is well-known, what mainly worried Einstein was the possibility of “non-local effects:” the subjective decision of an observer (who may choose among different <italic>incompatible observables</italic> to be measured on the system <italic>S</italic><sub>1</sub>) seems to determine the instantaneous emergence of an actual property for the system <italic>S</italic><sub>2</sub>, which might be very “far” from <italic>S</italic><sub>1</sub> (possibly inaccessible by means of a light-signal). Interestingly enough, in the framework of quantum computation, entangled states have been often used as a powerful resource, even from a technological point of view (for instance, in the applications to teleportation-phenomena and to quantum cryptography).</p><p>As expected, quantum computation cannot be identified with a “static” representation of pieces of information. What is important is the dynamic <italic>process</italic> of information that gives rise to quantum computations. Such process is mathematically performed by <italic>quantum logical gates</italic> (briefly, <italic>gates</italic>): special examples of <italic>unitary operators</italic> that transform quregisters into quregisters in a reversible way. Since in quantum theory the time-evolution of all physical systems is mathematically described by unitary operators, one can say that quantum computations can be regarded as the time-evolution of some special quantum objects.</p><p>We will now introduce the definition of <italic>quantum state machine</italic>, which represents a quantum counterpart of the classical notion of <italic>deterministic state machine</italic>. From an intuitive point of view, any quantum state machine can be regarded as a kind of quantum superposition of many classical deterministic state machines. Some definitions of <italic>quantum Turing machine</italic> discussed in the literature are based on a strong idealization: no limit is assumed for the length of the registers occurring in a computation. This corresponds to the classical assumption according to which a Turing machine is equipped with an infinite tape. We will consider a more realistic concept, closer to physical quantum computers, which are of course always bound to a limited memory.</p><p><bold>Definition 5</bold>. <italic>Quantum state machine</italic>.</p><p>A <italic>quantum state machine</italic> is an abstract system <bold>QM</bold> associated to a (finite-dimensional) Hilbert space <inline-formula><mml:math id="M52"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><bold>QM</bold></sup> whose unit-vectors |ψ〉 represent possible pure states of a quantum system that could physically implement the computations of the state machine. The space <inline-formula><mml:math id="M53"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><bold>QM</bold></sup> has the following form:
<disp-formula id="E21"><mml:math id="M54"><mml:mrow><mml:msup><mml:mi mathvariant="-tex-caligraphic">H</mml:mi><mml:mrow><mml:mstyle mathvariant="bold" mathsize="normal"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi></mml:mstyle></mml:mrow></mml:msup><mml:mo>=</mml:mo><mml:msup><mml:mi mathvariant="-tex-caligraphic">H</mml:mi><mml:mi>H</mml:mi></mml:msup><mml:mo>⊗</mml:mo><mml:msup><mml:mi mathvariant="-tex-caligraphic">H</mml:mi><mml:mi mathvariant="-tex-caligraphic">S</mml:mi></mml:msup><mml:mo>⊗</mml:mo><mml:msup><mml:mi mathvariant="-tex-caligraphic">H</mml:mi><mml:mi>W</mml:mi></mml:msup><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>The following conditions are required:
<list list-type="order"><list-item><p><inline-formula><mml:math id="M55"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><italic>H</italic></sup> (which represents the halting-space) is the space ℂ<sup>2</sup>, where the two elements of the canonical basis ({|0〉<sub><italic>H</italic></sub>, |1〉<sub><italic>H</italic></sub>}) correspond to the states “the machine does not halt” and “the machine halts,” respectively.</p></list-item><list-item><p><inline-formula><mml:math id="M56"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><inline-formula><mml:math id="M57"><mml:mi mathvariant="-tex-caligraphic">S</mml:mi></mml:math></inline-formula></sup> (which represents the internal-state space) is associated to a finite set <inline-formula><mml:math id="M58"><mml:mi mathvariant="-tex-caligraphic">S</mml:mi></mml:math></inline-formula> of classical internal states. We require that <inline-formula><mml:math id="M59"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><inline-formula><mml:math id="M60"><mml:mi mathvariant="-tex-caligraphic">S</mml:mi></mml:math></inline-formula></sup> = ⊗<sup><italic>m</italic></sup>ℂ<sup>2</sup>, where 2<sup><italic>m</italic></sup> is the cardinal number of <inline-formula><mml:math id="M61"><mml:mi mathvariant="-tex-caligraphic">S</mml:mi></mml:math></inline-formula>. Accordingly, the set <inline-formula><mml:math id="M62"><mml:mi mathvariant="-tex-caligraphic">S</mml:mi></mml:math></inline-formula> can be one-to-one associated to a basis of <inline-formula><mml:math id="M63"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><inline-formula><mml:math id="M64"><mml:mi mathvariant="-tex-caligraphic">S</mml:mi></mml:math></inline-formula></sup>.</p></list-item><list-item><p><inline-formula><mml:math id="M65"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><italic>W</italic></sup> (which represents the word-space) is identified with a Hilbert space ⊗<sup><italic>n</italic></sup>ℂ<sup>2</sup> (for a given <italic>n</italic> ≥ 1). The number <italic>n</italic> determines the length of the registers |<italic>x</italic><sub>1</sub>, …, <italic>x</italic><sub><italic>n</italic></sub>〉 that may occur in a computation. Shorter registers |<italic>x</italic><sub>1</sub>, …, <italic>x</italic><sub><italic>h</italic></sub>〉 (with <italic>h</italic> < <italic>n</italic>) can be represented in the space ⊗<sup><italic>n</italic></sup>ℂ<sup>2</sup> by means of convenient <italic>ancillary bits</italic>.</p><p>Let <italic>B</italic><sup><bold>QM</bold></sup> be a basis of <inline-formula><mml:math id="M66"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><bold>QM</bold></sup>, whose elements are unit-vectors having the following form:
<disp-formula id="E22"><mml:math id="M67"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>φ</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>h</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>s</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where |<italic>h</italic><sub><italic>i</italic></sub>〉 belongs to the basis of <inline-formula><mml:math id="M68"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><italic>H</italic></sup>, while |<italic>s</italic><sub><italic>i</italic></sub>〉 belongs to the basis of <inline-formula><mml:math id="M69"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><italic>S</italic></sup>.</p><p>Any unit-vector |ψ〉 of <inline-formula><mml:math id="M70"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><bold>QM</bold></sup> that is a superposition of basis-elements |φ<sub><italic>i</italic></sub>〉 represents a possible <italic>computational state</italic> of <bold>QM</bold>. The expected interpretation of a computational state
<disp-formula id="E23"><mml:math id="M71"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mi>ψ</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:munder><mml:mo>∑</mml:mo><mml:mi>i</mml:mi></mml:munder><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:mstyle><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>h</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>s</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow></mml:mrow></mml:math></disp-formula></p><p>is the following:
<list list-type="bullet"><list-item><p>the machine in state |ψ〉 might halt with probability <inline-formula><mml:math id="M72"><mml:mo>|</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msub><mml:msup><mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:math></inline-formula> (if |<italic>h</italic><sub><italic>i</italic></sub>〉 = |1<sub><italic>H</italic></sub>〉) or with probability <inline-formula><mml:math id="M73"><mml:mn>1</mml:mn><mml:mo>-</mml:mo><mml:mo>|</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msub><mml:msup><mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:math></inline-formula> (if |<italic>h</italic><sub><italic>i</italic></sub>〉 = |0<sub><italic>H</italic></sub>〉).</p></list-item><list-item><p>the machine in state |ψ〉 might correspond to the classical configuration (<italic>s</italic><sub><italic>i</italic></sub>, (<italic>x</italic><sub><italic>i</italic><sub>1</sub></sub>, …, <italic>x</italic><sub><italic>i</italic><sub><italic>n</italic></sub></sub>)) with probability <inline-formula><mml:math id="M74"><mml:mo>|</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow></mml:msub><mml:msup><mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:math></inline-formula>.</p><p>Hence, the state |ψ〉 describes a kind of <italic>quantum co-existence</italic> of different classical deterministic configurations.</p></list-item></list></p></list-item><list-item><p>The set of <italic>possible inputs</italic> of <bold>QM</bold> is identified with the set of all computational states that have the following form:
<disp-formula id="E24"><mml:math id="M75"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mi>ψ</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:munder><mml:mo>∑</mml:mo><mml:mi>i</mml:mi></mml:munder><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mi>H</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>s</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mi>n</mml:mi></mml:mrow></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow></mml:mrow></mml:mstyle><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p></list-item><list-item><p>Like a deterministic state machine, a quantum state machine <bold>QM</bold> is characterized by a <italic>program</italic>. In the quantum case, a program is identified with a sequence of unitary operators of <inline-formula><mml:math id="M76"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><bold>QM</bold></sup>:
<disp-formula id="E25"><mml:math id="M77"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mi>t</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where we may have: <italic>U</italic><sub><italic>i</italic></sub> = <italic>U</italic><sub><italic>j</italic></sub> with <italic>i</italic> ≠ <italic>j</italic>.</p><p>The following conditions are required:
<list list-type="alpha-lower"><list-item><p>for any possible input |ψ<sub>0</sub>〉, <italic>U</italic><sub>0</sub>(|ψ<sub>0</sub>〉) = |ψ<sub>1</sub>〉 is a superposition of basis-elements having the following form:
<disp-formula id="E26"><mml:math id="M78"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msubsup><mml:mi>h</mml:mi><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msubsup></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msubsup><mml:mi>s</mml:mi><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msubsup></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msubsup><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow><mml:mn>1</mml:mn></mml:msubsup><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msubsup><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow><mml:mn>1</mml:mn></mml:msubsup></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where all <inline-formula><mml:math id="M79"><mml:msubsup><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msubsup></mml:math></inline-formula> are different from <italic>s</italic><sub><italic>in</italic></sub> and <inline-formula><mml:math id="M80"><mml:mtext>|</mml:mtext><mml:msubsup><mml:mi>h</mml:mi><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msubsup><mml:mo>〉</mml:mo><mml:mo>=</mml:mo><mml:mtext> </mml:mtext><mml:mo>|</mml:mo><mml:msub><mml:mn>0</mml:mn><mml:mi>H</mml:mi></mml:msub><mml:mo>〉</mml:mo></mml:math></inline-formula>, if <italic>t</italic> ≠ 0.</p></list-item><list-item><p>For any <italic>j</italic> (0 < <italic>j</italic> < <italic>t</italic>), <italic>U</italic><sub><italic>j</italic></sub>(|ψ<sub><italic>j</italic></sub>〉) = |ψ<sub><italic>j</italic> + 1</sub>〉 is a superposition of basis-elements having the following form:
<disp-formula id="E27"><mml:math id="M81"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mi>H</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msubsup><mml:mi>s</mml:mi><mml:mi>i</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msubsup><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msubsup><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p></list-item><list-item><p><italic>U</italic><sub><italic>t</italic></sub>(|ψ<sub><italic>t</italic></sub>〉) = |ψ<sub><italic>t</italic> + 1</sub>〉 is a finite superposition of basis-elements having the following form:
<disp-formula id="E28"><mml:math id="M82"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mn>1</mml:mn><mml:mi>H</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>s</mml:mi><mml:mrow><mml:mi>h</mml:mi><mml:mi>a</mml:mi><mml:mi>l</mml:mi><mml:msub><mml:mi>t</mml:mi><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msubsup><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow><mml:mrow><mml:mi>t</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msubsup><mml:mi>x</mml:mi><mml:mrow><mml:msub><mml:mi>i</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow><mml:mrow><mml:mi>t</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p></list-item></list></p></list-item></list></p><p>The concept of <italic>computation</italic> of a quantum state machine can be now defined in a natural way.</p><p><bold>Definition 6</bold>. <italic>Computation of a quantum state machine</italic>.</p><p>Let <bold>QM</bold> be a quantum state machine, whose program is the operator-sequence (<italic>U</italic><sub>0</sub>, …, <italic>U</italic><sub><italic>t</italic></sub>) and let |ψ<sub>0</sub>〉 be a possible input of <bold>QM</bold>. A <italic>computation</italic> of <bold>QM</bold> with input |ψ<sub>0</sub>〉 is a sequence of computational states of <bold>QM</bold><disp-formula id="E29"><mml:math id="M83"><mml:mrow><mml:mi mathvariant="-tex-caligraphic">Q</mml:mi><mml:mi mathvariant="-tex-caligraphic">C</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>ψ</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>ψ</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula>such that: |ψ<sub><italic>i</italic> + 1</sub>〉 = <italic>U</italic><sub><italic>i</italic></sub>(|ψ<sub><italic>i</italic></sub>〉), for any <italic>i</italic> (0 ≤ <italic>i</italic> ≤ <italic>t</italic>).</p><p>The vector |ψ<sub><italic>t</italic> + 1</sub>〉 represents the output of the computation, while the density operator <inline-formula><mml:math id="M84"><mml:mi>R</mml:mi><mml:mi>e</mml:mi><mml:msup><mml:mi>d</mml:mi><mml:mn>3</mml:mn></mml:msup><mml:mo stretchy="false">(</mml:mo><mml:mtext>|</mml:mtext><mml:msub><mml:mi>ψ</mml:mi><mml:mrow><mml:mi>t</mml:mi><mml:mtext> </mml:mtext><mml:mo>+</mml:mo><mml:mtext> </mml:mtext><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">〉</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math></inline-formula> (the reduced state of |ψ<sub><italic>t</italic> + 1</sub>〉 with respect to the third subsystem) represents the word-output of the computation.</p><p>Like all abstract notions of <italic>quantum computer</italic>, the concept of <italic>quantum state machine</italic> gives rise to some critical questions that have been often discussed in the literature. Two important problems (which cannot have any counterpart in the case of classical computation) are the following:</p><list list-type="bullet"><list-item><p>How shall we interpret the operation of “reading the output” of a computation of a given machine? What is the role of the <italic>collapse of the wave-function</italic> during a reading-action?</p></list-item><list-item><p>Is it possible to measure the halting state without disturbing the configuration-state?</p></list-item></list><p>Consider now a quantum state machine whose program is
<disp-formula id="E30"><mml:math id="M85"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mi>t</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Each <italic>U</italic><sub><italic>i</italic></sub> naturally determines a corresponding word-operator <inline-formula><mml:math id="M86"><mml:msubsup><mml:mrow><mml:mi>U</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi></mml:mrow><mml:mrow><mml:mi>W</mml:mi></mml:mrow></mml:msubsup></mml:math></inline-formula>, defined on the word-space <inline-formula><mml:math id="M87"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><italic>W</italic></sup>. Generally, it is not guaranteed that all word-operators are unitary. But it is convenient to refer to quantum state machines that satisfy this condition. In this way, any quantum state machine (whose word-space is ⊗<sup><italic>n</italic></sup>ℂ<sup>2</sup>) determines a <italic>quantum circuit</italic>, consisting of a sequence of unitary operators (<italic>gates</italic>):
<disp-formula id="E31"><mml:math id="M88"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msubsup><mml:mi>U</mml:mi><mml:mn>0</mml:mn><mml:mi>W</mml:mi></mml:msubsup><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msubsup><mml:mi>U</mml:mi><mml:mi>t</mml:mi><mml:mi>W</mml:mi></mml:msubsup><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where <italic>n</italic> represents the <italic>width</italic>, while <italic>t</italic> + 1 represents the <italic>depth</italic> of the circuit.</p><p>To what extent can quantum state machines be simulated by classical probabilistic state machines? In order to discuss this important question, let us refer to a celebrated quantum experiment, based on the <italic>Mach–Zehnder interferometer</italic> (represented by Figure <xref ref-type="fig" rid="F2">2</xref>).</p><fig id="F2" position="float"><label>Figure 2</label><caption><p><bold>The Mach–Zehnder interferometer</bold>.</p></caption><graphic xlink:href="fpsyg-06-01583-g0002"></graphic></fig><p>The physical situation can be sketched as follows. Consider a photon-beam (possibly consisting of a single photon) and assume that |0〉 describes the state of photons moving along the <italic>x</italic> direction, while |1〉 describes the state of photons moving along the <italic>y</italic> direction. All photons go through a first <italic>beam splitter</italic> that “splits” them giving rise to the following effect: within the box each photon follows a path corresponding either to the <italic>x</italic>-direction or to the <italic>y</italic>-direction with probability <inline-formula><mml:math id="M89"><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:math></inline-formula>. Soon after, on both paths, all photons are reflected by a <italic>mirror</italic> that inverts their direction. Finally, the photons pass through a second beam splitter that determines the output-state. Suppose that all photons entering into the interferometer-box are moving in the <italic>x</italic>-direction. According to a “classical way of thinking” we would expect that the photons detected at the end of the process will move either along the <italic>x</italic>-direction or along the <italic>y</italic>-direction with probability <inline-formula><mml:math id="M90"><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:math></inline-formula>. The result of the experiment is, instead, completely different: the Mach–Zehnder interferometer <italic>always</italic> transforms the input-state |0〉 into the output-state |0〉; while the input-state |1〉 is transformed into |1〉.</p><p>From a mathematical point of view, such a “surprising” result can be explained by using, in an essential way, the concept of superposition. The apparatuses (used in the Mach–Zehnder experiment) can be mathematically represented by two important gates. A beam splitter can be regarded as a physical implementation of the <italic>Hadamard-gate</italic><inline-formula><mml:math id="M91"><mml:msqrt><mml:mrow><mml:mstyle class="text"><mml:mtext class="texttt" mathvariant="monospace">I</mml:mtext></mml:mstyle></mml:mrow></mml:msqrt></mml:math></inline-formula> (also called <italic>square root of identity</italic>), which is defined as follows (on the canonical basis of ℂ<sup>2</sup>):
<disp-formula id="E32"><mml:math id="M92"><mml:mrow><mml:msqrt><mml:mi mathvariant="monospace">I</mml:mi></mml:msqrt><mml:mrow><mml:mo>|</mml:mo><mml:mn>0</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mn>0</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>+</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mn>1</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mo>;</mml:mo><mml:msqrt><mml:mi mathvariant="monospace">I</mml:mi></mml:msqrt><mml:mrow><mml:mo>|</mml:mo><mml:mn>1</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mn>0</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>−</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mn>1</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Apparently, the Hadamard-gate transforms the two classical bits |0〉 and |1〉 into two (different) genuine superpositions. As a consequence, within the Mach–Zehnder box a photon in state <inline-formula><mml:math id="M93"><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">(</mml:mo><mml:mo>|</mml:mo><mml:mn>0</mml:mn><mml:mo>〉</mml:mo><mml:mo>+</mml:mo><mml:mo>|</mml:mo><mml:mn>1</mml:mn><mml:mo>〉</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math></inline-formula> turns out to satisfy at the same time two alternative properties: the property of moving along the <italic>x</italic>-direction and the property of moving along the <italic>y</italic>-direction. We have here a characteristic quantum parallelism: a single photon “goes along” two different paths at the same time! Metaphorically, situations of this kind have been sometimes compared to the puzzling behavior of a “quantum skier” who runs at the same time on the left and on the right side of a given tree (see Figure <xref ref-type="fig" rid="F3">3</xref>).</p><fig id="F3" position="float"><label>Figure 3</label><caption><p><bold>The quantum skier</bold>.</p></caption><graphic xlink:href="fpsyg-06-01583-g0003"></graphic></fig><p>The second apparatus of the Mach–Zehnder interferometer (the mirror), can be regarded as a physical implementation of another important gate, the <italic>negation</italic><monospace>NOT</monospace> (a quantum generalization of the classical negation), which is defined as follows:
<disp-formula id="E33"><mml:math id="M94"><mml:mrow><mml:mi mathvariant="monospace">N</mml:mi><mml:mi mathvariant="monospace">O</mml:mi><mml:mi mathvariant="monospace">T</mml:mi><mml:mrow><mml:mo>|</mml:mo><mml:mn>0</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mn>1</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>;</mml:mo><mml:mi mathvariant="monospace">N</mml:mi><mml:mi mathvariant="monospace">O</mml:mi><mml:mi mathvariant="monospace">T</mml:mi><mml:mrow><mml:mo>|</mml:mo><mml:mn>1</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mn>0</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Accordingly, the <italic>Mach–Zehnder circuit</italic> can be identified with the following sequence of three gates (all defined on the space ℂ<sup>2</sup>):
<disp-formula id="E34"><mml:math id="M95"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi mathvariant="monospace">I</mml:mi></mml:msqrt><mml:mo>,</mml:mo><mml:mi mathvariant="monospace">N</mml:mi><mml:mi mathvariant="monospace">O</mml:mi><mml:mi mathvariant="monospace">T</mml:mi><mml:mo>,</mml:mo><mml:msqrt><mml:mi mathvariant="monospace">I</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Let us now apply the Mach–Zehnder circuit to the input |0〉. We obtain:</p><p><inline-formula><mml:math id="M96"><mml:msqrt><mml:mtext mathvariant="monospace">I</mml:mtext></mml:msqrt><mml:mo>:</mml:mo><mml:mtext> |</mml:mtext><mml:mn>0</mml:mn><mml:mo>〉</mml:mo><mml:mtext> </mml:mtext><mml:mo>↦</mml:mo><mml:mtext> </mml:mtext><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">(</mml:mo><mml:mtext>|</mml:mtext><mml:mn>0</mml:mn><mml:mo>〉</mml:mo><mml:mo>+</mml:mo><mml:mtext> |</mml:mtext><mml:mn>1</mml:mn><mml:mo>〉</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>;</mml:mo><mml:mtext mathvariant="monospace">NOT </mml:mtext><mml:mo>:</mml:mo><mml:mtext> </mml:mtext><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">(</mml:mo><mml:mtext>|</mml:mtext><mml:mn>0</mml:mn><mml:mo>〉</mml:mo><mml:mo>+</mml:mo><mml:mtext> |</mml:mtext><mml:mn>1</mml:mn><mml:mo>〉</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mtext> </mml:mtext><mml:mo>↦</mml:mo><mml:mtext> </mml:mtext><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">(</mml:mo><mml:mtext>|</mml:mtext><mml:mn>0</mml:mn><mml:mo>〉</mml:mo><mml:mo>+</mml:mo><mml:mtext> |</mml:mtext><mml:mn>1</mml:mn><mml:mo>〉</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>;</mml:mo><mml:mtext> </mml:mtext><mml:msqrt><mml:mtext mathvariant="monospace">I</mml:mtext></mml:msqrt><mml:mo>:</mml:mo><mml:mtext> </mml:mtext><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">(</mml:mo><mml:mtext>|</mml:mtext><mml:mn>0</mml:mn><mml:mo>〉</mml:mo><mml:mo>+</mml:mo><mml:mtext> |</mml:mtext><mml:mn>1</mml:mn><mml:mo>〉</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>↦</mml:mo><mml:mtext> |</mml:mtext><mml:mn>0</mml:mn><mml:mo>〉</mml:mo></mml:math></inline-formula>.</p><p>We can see, in this way, how the Mach–Zehnder circuit transforms the input-state |0〉 into the output-state |0〉. In a similar way, the input-state |1〉 is transformed into the output-state |1〉.</p><p>Is there any natural “classical counterpart” for the Hadamard-gate? A natural candidate might be a particular example of a probabilistic state machine that we can conventionally call <italic>the classical probabilistic <monospace>NOT</monospace></italic><italic>-state machine</italic> (<bold>PM</bold><sup><monospace>NOT</monospace></sup>). Such machine can be defined as follows:</p><list list-type="bullet"><list-item><p>The set of possible word-inputs of <bold>PM</bold><sup><monospace>NOT</monospace></sup> is the set of words {(0), (1)}.</p></list-item><list-item><p>The program of <bold>PM</bold><sup><monospace>NOT</monospace></sup> consists of the following sequence of rules:
<disp-formula id="E35"><mml:math id="M97"><mml:mrow><mml:mi>S</mml:mi><mml:mi>e</mml:mi><mml:msub><mml:mi>q</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>R</mml:mi><mml:mrow><mml:msub><mml:mn>0</mml:mn><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p></list-item></list><p>where:</p><p><italic>R</italic><sub>0<sub>1</sub></sub> : (<italic>s</italic><sub><italic>in</italic></sub>, (<italic>x</italic>)) ↦ (<italic>s</italic><sub><italic>halt</italic><sub><italic>j</italic></sub></sub>, (<italic>x</italic>)) and <inline-formula><mml:math id="M98"><mml:mi>p</mml:mi><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:msub><mml:mrow><mml:mi>R</mml:mi></mml:mrow><mml:mrow><mml:msub><mml:mrow><mml:mn>0</mml:mn></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:msub></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:math></inline-formula>;</p><p><italic>R</italic><sub>0<sub>2</sub></sub> : (<italic>s</italic><sub><italic>in</italic></sub>, (<italic>x</italic>)) ↦ (<italic>s</italic><sub><italic>halt</italic><sub><italic>j</italic></sub></sub>, (1 − <italic>x</italic>)) and <inline-formula><mml:math id="M99"><mml:mi>p</mml:mi><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:msub><mml:mrow><mml:mi>R</mml:mi></mml:mrow><mml:mrow><mml:msub><mml:mrow><mml:mn>0</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:msub></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:math></inline-formula>.</p><p>Consider, for instance, the input (<italic>s</italic><sub><italic>in</italic></sub>, (0)). The output will be the following set:
<disp-formula id="E37"><mml:math id="M100"><mml:mrow><mml:mrow><mml:mo>{</mml:mo><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mrow><mml:mi>h</mml:mi><mml:mi>a</mml:mi><mml:mi>l</mml:mi><mml:msub><mml:mi>t</mml:mi><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>0</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mrow><mml:mi>h</mml:mi><mml:mi>a</mml:mi><mml:mi>l</mml:mi><mml:msub><mml:mi>t</mml:mi><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mo>}</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>On this basis, a “classical probabilistic Mach–Zehnder state machine” would determine (for the word-input (0)) the word-graph illustrated by Figure <xref ref-type="fig" rid="F4">4</xref>.</p><fig id="F4" position="float"><label>Figure 4</label><caption><p><bold>A word-graph for a “classical probabilistic Mach–Zehnder state machine”</bold>.</p></caption><graphic xlink:href="fpsyg-06-01583-g0004"></graphic></fig><p>Such a machine turns out to compute both the words (0) and (1) with probability <inline-formula><mml:math id="M101"><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:math></inline-formula>. Interestingly enough, this is the same probabilistic result that is obtained in the quantum case, when one performs a measurement inside the interferometer-box. In such a case, photons behave like “normal skiers,” who pass <italic>either</italic> at the right <italic>or</italic> at the left side of a tree (where <italic>or</italic> represents here, of course, the exclusive disjunction).</p><p>The arguments we have developed seem to confirm the following conjecture: the characteristic superposition-patterns, that may occur during a quantum computation (when no measurement is performed during the computation-process), cannot be generally represented by probabilistic state machines. Quantum parallelism (based on superpositions) and classical parallelism are deeply different.</p></sec><sec id="s4"><title>4. Quantum parallelism, psychological parallelism, and quantum computational semantics</title><p>What kind of similarity can be recognized between quantum parallel structures and different forms of psychological parallelism? Trying to represent the human mind as a kind of system of quantum state machines would be, of course, naive and misleading. In spite of many important results in the framework of neurosciences, the complex network that connects human conscious and unconscious thoughts is still quite mysterious<xref ref-type="fn" rid="fn0007"><sup>7</sup></xref>. Quantum-like superpositions can be reasonably applied to represent some aspects of such complex networks. Even quantum <italic>interference phenomena</italic> (with the characteristic constructive and destructive effects) can find some natural psychological interpretations.</p><p>According to an interesting hypothesis (discussed by the neuroscientist Boncinelli, <xref rid="B4" ref-type="bibr">2012</xref>), the mysterious emergence of an <italic>act of consciousness</italic> can be represented as a sudden transition from a parallel structure to a linear one. Is it reasonable to conjecture that such transition could be described as a kind of “psychological collapse of the wave-function?”</p><p>In the investigations about possible links between <italic>quantum structures</italic> and <italic>psychological structures</italic> a useful tool is represented by a special form of quantum logical semantics (called <italic>quantum computational semantics</italic>) that has been naturally inspired by the theory of quantum computation<xref ref-type="fn" rid="fn0008"><sup>8</sup></xref>.</p><p>Let us briefly recall the basic ideas of this semantics. We can refer a first-order language <inline-formula><mml:math id="M102"><mml:mi mathvariant="-tex-caligraphic">L</mml:mi></mml:math></inline-formula>, whose non-logical alphabet contains individual terms (variables and names), predicates and sentential constants. Interpreting the language <inline-formula><mml:math id="M103"><mml:mi mathvariant="-tex-caligraphic">L</mml:mi></mml:math></inline-formula> means associating to any formula α a <italic>meaning</italic>, identified with a piece of quantum information that can be stored by a quantum system. Accordingly, any possible meaning of α is represented by a possible (pure or mixed) state of a quantum system: generally, a density operator ρ<sub>α</sub> that lives in a Hilbert space <inline-formula><mml:math id="M104"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup>α</sup>, whose dimension depends on the linguistic complexity of α.</p><p>The logical operators of <inline-formula><mml:math id="M105"><mml:mi mathvariant="-tex-caligraphic">L</mml:mi></mml:math></inline-formula> are associated to special examples of Hilbert-space operations that have a characteristic dynamic behavior, representing possible computation-actions. The logical connectives are interpreted as particular (reversible) gates, like the negation <monospace>NOT</monospace>, the Hadamard-gate <inline-formula><mml:math id="M106"><mml:msqrt><mml:mrow><mml:mstyle class="text"><mml:mtext class="texttt" mathvariant="monospace">I</mml:mtext></mml:mstyle></mml:mrow></mml:msqrt></mml:math></inline-formula>, the Toffoli-gate <monospace>T</monospace> (which allows us to define a reversible conjunction <monospace>AND</monospace>). At the same time, the logical quantifiers (∀, ∃) are interpreted as possibly irreversible quantum operations. Since the universe of discourse (which the language refers to) may be indeterminate, the use of quantum quantifiers may give rise to a reversibility-breaking, which is quite similar to what happens in the case of measurement-phenomena.</p><p>Due to the characteristic features of quantum holism, meanings turn out to behave in a <italic>holistic</italic> and <italic>contextual</italic> way: the density operator ρ<sub>α</sub> (which represents the <italic>global</italic> meaning of a formula α) determines the <italic>contextual meanings</italic> of all parts of α (which can be obtained by applying the <italic>reduced-state function</italic> to ρ<sub>α</sub>). As a consequence, it may happen that the meaning of a formula is an entangled pure state, while the meanings of its parts are proper mixtures. In such cases, the meaning of a global expression turns out to be more precise than the meanings of its parts. It is also admitted that one and the same formula receives different contextual meanings in different contexts.</p><p>As an example, consider the atomic sentence “Alice is pretty” (formalized as <bold>Pa</bold>). In order to store the information expressed by this sentence, we need three quantum objects whose states represent the pieces of information corresponding, respectively, to the predicate <bold>P</bold>, to the name <bold>a</bold> and to the truth-degree according to which the individual denoted by the name <bold>a</bold> satisfies the property denoted by the predicate <bold>P</bold>. Accordingly, the meaning of the sentence <bold>Pa</bold> can be identified with a (pure or mixed) state ρ<sub><bold>Pa</bold></sub> living in the tensor-product space <inline-formula><mml:math id="M107"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup><bold>Pa</bold></sup> = ⊗<sup>3</sup>ℂ<sup>2</sup>. In order to obtain the contextual meanings of the linguistic parts of <bold>Pa</bold> it is sufficient to consider the two reduced states <italic>Red</italic><sup>1</sup>(ρ<sub><bold>Pa</bold></sub>) and <italic>Red</italic><sup>2</sup>(ρ<sub><bold>Pa</bold></sub>), which describe (respectively) the states of the first and of the second subsystem of the quantum object that stores the information expressed by the sentence <bold>Pa</bold>. From a logical point of view, <italic>Red</italic><sup>1</sup>(ρ<sub><bold>Pa</bold></sub>) and <italic>Red</italic><sup>2</sup>(ρ<sub><bold>Pa</bold></sub>) can be regarded as two <italic>intensional meanings</italic>: a property-concept and an individual concept, respectively; while ρ<sub><bold>Pa</bold></sub> represents a <italic>propositional concept</italic> (or <italic>event</italic>).</p><p>Like formulas, sequences of formulas also can be interpreted according to the quantum computational rules. As expected, a possible meaning of the sequence (α<sub>1</sub>, …, α<sub><italic>n</italic></sub>) will be a density operator ρ<sub>(<sub>α</sub><sub>1</sub>, …, α<sub><italic>n</italic></sub>)</sub> living in a Hilbert space <inline-formula><mml:math id="M108"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sup>(α<sub>1</sub>,…,α<sub><italic>n</italic></sub>)</sup>, whose dimension depends on the linguistic complexity of the formulas α<sub>1</sub>, …, α<sub><italic>n</italic></sub>.</p><p>In this framework one can develop an abstract theory of <italic>vague possible worlds</italic>. Consider a pair
<disp-formula id="E38"><mml:math id="M109"><mml:mrow><mml:mi>W</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>α</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>α</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>ρ</mml:mi><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>α</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>α</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula>consisting of a sequence of formulas and of a density operator that represents a possible meaning for our sequence. It seems reasonable to assume that <italic>W</italic> describes a <italic>vague possible world</italic>, a kind of <italic>abstract scene</italic> where most events are characterized by a “cloud of ambiguities,” due to quantum uncertainties. In some cases <italic>W</italic> might be exemplified as a “real” scene of a theatrical play or as a vague situation that is described either in a novel or in a poem. And it is needless to recall how ambiguities play an essential role in literary works.</p><p>As an example, consider the following vague possible world:
<disp-formula id="E39"><mml:math id="M110"><mml:mrow><mml:mi>W</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mstyle mathvariant="bold" mathsize="normal"><mml:mi>P</mml:mi><mml:mi>a</mml:mi><mml:mi>b</mml:mi></mml:mstyle><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>ρ</mml:mi><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mstyle mathvariant="bold" mathsize="normal"><mml:mi>P</mml:mi><mml:mi>a</mml:mi><mml:mi>b</mml:mi></mml:mstyle><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where <bold>Pab</bold> is supposed to formalize the sentence “Alice is kissing Bob,” while ρ<sub><bold>Pab</bold></sub> corresponds to the pure state
<disp-formula id="E40"><mml:math id="M111"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>Ψ</mml:mi><mml:mrow><mml:mstyle mathvariant="bold" mathsize="normal"><mml:mi>P</mml:mi><mml:mi>a</mml:mi><mml:mi>b</mml:mi></mml:mstyle></mml:mrow></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mi>φ</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>⊗</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mn>2</mml:mn></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mo>⊗</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mn>1</mml:mn><mml:mo>〉</mml:mo></mml:mrow><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula>where |φ〉 lives in the space ℂ<sup>2</sup>, while |Ψ〉<sub><bold>Pab</bold></sub> lives in the space ⊗<sup>4</sup>ℂ<sup>2</sup>. Here the reduced state of |Ψ〉<sub><bold>Pab</bold></sub> that describes the pair (Alice, Bob) has the typical form of an entangled state; consequently, the states describing the two individuals Alice and Bob are two identical mixed states. In the context |Ψ〉<sub><bold>Pab</bold></sub> Alice and Bob turn out to be indistinguishable: it is not determined “who is who” and “who is kissing whom.” It is not difficult to imagine some “real” theatrical scenes representing ambiguous situations of this kind.</p></sec><sec id="s5"><title>5. A quantum semantics for music</title><p>An abstract version of the quantum computational semantics can be applied to a formal analysis of musical compositions, where both <italic>musical ideas</italic> and <italic>extra-musical meanings</italic> are generally characterized by some essentially vague and ambiguous features<xref ref-type="fn" rid="fn0009"><sup>9</sup></xref>.</p><p>Any musical composition (say, a sonata, a symphony, an opera,…) is, generally, determined by three elements:</p><list list-type="bullet"><list-item><p>a <italic>score</italic>;</p></list-item><list-item><p>a set of <italic>performances</italic>;</p></list-item><list-item><p>a set of musical <italic>thoughts</italic> (or <italic>ideas</italic>), which represent possible <italic>meanings</italic> for the <italic>musical phrases</italic> written in the score.</p></list-item></list><p>While scores represent the syntactical component of musical compositions, performances are physical events that occur in space and time. From a logical point of view, we could say that performances are, in a sense, similar to <italic>extensional meanings</italic>, i.e., well-determined systems of objects which the linguistic expressions refer to.</p><p>Musical thoughts (or ideas) represent, instead, a more mysterious element. Is it reasonable to assume the existence of such ideal objects that are, in a sense, similar to the <italic>intensional meanings</italic> investigated by logic? Is there any danger to adhere, in this way, to a form of <italic>Platonism</italic>? When discussing semantic questions, one should not be “afraid” of Platonism. In the particular case of music, a composition cannot be simply reduced to a score and to a system of sound-events. Between a score (which is a system of signs) and the sound-events created by a performance there is something intermediate, represented by the musical ideas that underlie the different performances. This is the abstract environment where normally live both composers and conductors, who are accustomed to study scores without any help of a material instrument.</p><p>Following the rules of the quantum semantics, <italic>musical ideas</italic> can be naturally represented as superpositions that ambiguously describe a variety of co-existent thoughts. Accordingly, we can write:
<disp-formula id="E41"><mml:math id="M112"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mi>μ</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:munder><mml:mo>∑</mml:mo><mml:mi>i</mml:mi></mml:munder><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:mstyle><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>μ</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula></p><p>where:</p><list list-type="bullet"><list-item><p>|μ〉 is an abstract object representing a musical idea that <italic>alludes</italic> to other ideas |μ<sub><italic>i</italic></sub>〉 (possible <italic>variants</italic> of |μ〉 that are, in a sense, all co-existent);</p></list-item><list-item><p>the number <italic>c</italic><sub><italic>i</italic></sub> measures the “weigth” of the component |μ<sub><italic>i</italic></sub>〉 in the context |μ〉.</p></list-item></list><p>As happens in the case of composite quantum systems, musical ideas (which represent possible meanings of <italic>musical phrases</italic> written in a score) have an essential <italic>holistic</italic> behavior: the meaning of a global musical phrase determines the <italic>contextual meanings</italic> of all its parts (and not the other way around).</p><p>An important feature of music is the capacity of <italic>evoking</italic> extra-musical meanings: subjective feelings, situations that are vaguely imagined by the composer or by the interpreter or by the listener, real or virtual theatrical scenes (which play an essential role in the case of lyric operas and of <italic>Lieder</italic>). The interplay between musical ideas and extra-musical meanings can be naturally represented in the framework of our quantum semantics, where extra-musical meanings can be dealt with as special examples of vague possible worlds.</p><p>We can refer to the abstract tensor product of two spaces</p><disp-formula id="E42"><mml:math id="M113"><mml:mrow><mml:mi>M</mml:mi><mml:mi>S</mml:mi><mml:mi>p</mml:mi><mml:mi>a</mml:mi><mml:mi>c</mml:mi><mml:mi>e</mml:mi><mml:mo>⊗</mml:mo><mml:mi>W</mml:mi><mml:mi>S</mml:mi><mml:mi>p</mml:mi><mml:mi>a</mml:mi><mml:mi>c</mml:mi><mml:mi>e</mml:mi><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula><p>where:</p><list list-type="bullet"><list-item><p><italic>MSpace</italic> represents the space of musical ideas |μ〉.</p></list-item><list-item><p><italic>WSpace</italic> represents the space of vague possible worlds, dealt with as special examples of abstract objects |<italic>w</italic>〉 that can be evoked by musical ideas.</p></list-item></list><p>Following the quantum-theoretic formalism, we can distinguish between <italic>factorized</italic> and <italic>non-factorized</italic> global musical ideas. A factorized global musical idea will have the form:
<disp-formula id="E43"><mml:math id="M114"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mi>M</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mi>μ</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>⊗</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mi>w</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>But we might also meet entangled global musical ideas, having the form:
<disp-formula id="E44"><mml:math id="M115"><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mi>M</mml:mi><mml:mo>〉</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:msub><mml:mi>c</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>μ</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>⊗</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>w</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:msub><mml:mi>c</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>μ</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo>⊗</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:msub><mml:mi>w</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow><mml:mo>〉</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>As is well-known, music gives rise to a special kind of psychological experience, where some complex parallel structures are consciously grasped, in a way that may appear miraculous. Paradigmatic examples arise, for instance, in the case of trios or quartets of lyric operas. In such cases, the listener perceives a <italic>global polyphonic structure</italic>; at the same time, he/she is able to follow (at least to a certain extent) the different melodic lines and even the different thoughts and feelings of the characters who are singing. As an example, it may be interesting to consider three great masterpieces of the history of lyric operas: the quartet of Act 1 in Beethoven's <italic>Fidelio</italic>, the quartet of Act 3 in Verdi's <italic>Rigoletto</italic> and the trio of Act 3 of <italic>Der Rosenkavalier</italic> by Richard Strauss. The parallel structures that arise in these three examples have some significant differences both from the musical and from the semantic point of view.</p><p>In <italic>Fidelio</italic>'s quartet the psychological contraposition between the four characters (Marzelline, Leonore, Rocco, Jaquino) is realized by means of a single musical theme that is successively sung by the four singers (Figure <xref ref-type="fig" rid="F5">5</xref>).</p><fig id="F5" position="float"><label>Figure 5</label><caption><p><bold>The quartet-theme</bold>.</p></caption><graphic xlink:href="fpsyg-06-01583-g0005"></graphic></fig><p>It is amazing how Beethoven succeeds in expressing, by one and the same theme, different attitudes and emotions: the joyful hope of Marzelline, the doubts and the anguish of Leonore, the paternal satisfaction of Rocco, the jealous rage of Jaquino. The whole context is dominated by strong ambiguities and antagonistic elements: the contrast between an improbable family-portrait and the cruel jail-environment, the contradictions of Rocco (who is at the same time a fond father and an accomplice of the prison-system), the sexual ambiguity of Leonore, the loving heroin who has disguised herself as a man (Fidelio), in the attempt to save her husband, the prisoner Florestan. The musical result is an extraordinary and highly emotional polyphonic construction based on very simple musical components.</p><p>The structure of <italic>Rigoletto</italic>'s quartet is completely different. All characters are associated to specific musical themes that are repeated with some variations. The leading musical idea is represented by the wonderful theme sung by the Duke of Mantova at the very beginning (Figure <xref ref-type="fig" rid="F6">6</xref>)<xref ref-type="fn" rid="fn0010"><sup>10</sup></xref>.</p><fig id="F6" position="float"><label>Figure 6</label><caption><p><bold>The Duke</bold>.</p></caption><graphic xlink:href="fpsyg-06-01583-g0006"></graphic></fig><p>Like Mozart's <italic>Don Giovanni</italic>, Verdi's Duke is a cynic seducer, who may appear sweet and sincere with his victims. And music often exalts a paradoxical co-existence of contradictory psychological attitudes. All contrasts are emphasized in the quartet by the sordid environment, where a crime is going to be committed. Maddalena's answer to the Duke is based on a fully different theme, a <italic>staccato</italic>-sequence of sixteenth-notes (Figure <xref ref-type="fig" rid="F7">7</xref>)<xref ref-type="fn" rid="fn0011"><sup>11</sup></xref>.</p><fig id="F7" position="float"><label>Figure 7</label><caption><p><bold>Maddalena</bold>.</p></caption><graphic xlink:href="fpsyg-06-01583-g0007"></graphic></fig><p>Both the music and the text reflect Maddalena's ambiguity: she is a prostitute who is playing a traditional seductive role; at the same time she is also instrumental to a murder-project. Gilda's entrance (soon after Maddalena's first phrase) determines a sudden dramatic change. What Gilda sings is a cry of sorrow, interrupted by some short pauses and <italic>appoggiaturas</italic> that seem to describe desperate sobs (Figure <xref ref-type="fig" rid="F8">8</xref>)<xref ref-type="fn" rid="fn0012"><sup>12</sup></xref>.</p><fig id="F8" position="float"><label>Figure 8</label><caption><p><bold>Gilda</bold>.</p></caption><graphic xlink:href="fpsyg-06-01583-g0008"></graphic></fig><p>One has often discussed the reasons that may have led Gilda to her unreasonable sacrifice for an unworthy man who had deceived her. Representing Gilda as a naive and modest girl is, however, misleading and in contrast with the greatness expressed by the music. Gilda's death-choice can be perhaps better understood as a suicide, caused by an unendurable disillusion. Rigoletto's role in the quartet is musically less “visible.” His mind is completely absorbed in the vengeance-project (“la vendetta”) that shall be shortly accomplished. From a musical point of view, the quartet is constructed as a polyphonic structure, where the four voices are interlaced, each preserving its own musical, semantic and psychological autonomy.</p><p><italic>Der Rosenkavalier</italic> by Strauss belongs to a musical and literary world that is somewhat far both from <italic>Fidelio</italic> and from <italic>Rigoletto</italic>. Different forms of ambiguity are exalted in this opera, which is characterized by an extraordinary unity of music and text, written by the great poet Hugo von Hofmannsthal. The theme of sexual ambiguity is here developed by the character of Octavian, the <italic>Rosenkavalier</italic> whose role is sung by a mezzo-soprano. Although Octavian may recall Mozart's Cherubino, ambiguities are in Strauss' opera more sophisticated: in two different situations Octavian disguises himself as a woman in order to make fun of the rude fiancé of the fascinating girl Sophie. Interestingly enough, some interpreters of the role of Octavian have told how often they have been puzzled by their “oscillating identity” during the opera's performance.</p><p>A different and deeper “identity-question” is evoked in a splendid aria sung by the <italic>Marschallin</italic> in Act 1. After a passionate night spent with her lover Octavian, the lady is troubled by some sad thoughts about the flowing of time and the mysterious co-existence of different identities of one and the same person in different stages of life. She sings:</p><disp-quote><p><italic>Aber wie kann das wirklich sein</italic>,</p><p><italic>dass ich die kleine Resi war</italic>,</p><p>und dass ich einmal die alte Frau sein werd'</p><p>.......................................</p><p>Wie kann denn das geschehen?</p><p>Wie macht denn das der liebe Gott?</p><p><italic>Wo ich doch immer die gleiche bin</italic>.</p><p><italic>Und wenn er's schon so machen muss</italic>,</p><p>warum lasst er mich denn zuschaun dabei</p><p>mit gar so klarem Sinn?</p><p>Warum versteckt er's nicht vor mir?</p><p><italic>Das alles ist geheim, so viel geheim</italic><xref ref-type="fn" rid="fn0013"><sup>13</sup></xref>.</p></disp-quote><p>One is dealing with an extraordinary poetic and musical representation of a “hard” scientific and philosophical problem, that modern philosophers of science usually call “the genidentity-question”<xref ref-type="fn" rid="fn0014"><sup>14</sup></xref>.</p><p>The trio performed at the end of the opera by three female voices (the Marschallin, Sophie, Octavian) is a wonderful polyphonic construction, where the three characters express different thoughts and feelings, which are not generally associated to some specific musical themes (unlike the case of <italic>Rigoletto</italic>'s quartet). The main theme is sung at the very beginning by the Marschallin (Figure <xref ref-type="fig" rid="F9">9</xref>)<xref ref-type="fn" rid="fn0015"><sup>15</sup></xref>.</p><fig id="F9" position="float"><label>Figure 9</label><caption><p><bold>The Marschallin</bold>.</p></caption><graphic xlink:href="fpsyg-06-01583-g0009"></graphic></fig><p>By this deeply moving musical phrase the Marschallin expresses her extreme act of love, which is to renounce love. Her choice might recall what Violetta Valery sings in Verdi's <italic>La Traviata:</italic></p><disp-quote><p><italic>Dite alla giovine sì bella e pura</italic><xref ref-type="fn" rid="fn0016"><sup>16</sup></xref></p></disp-quote><p>although Violetta and the Marschallin are, of course, completely different characters.</p><p>Sophie's entrance in the trio is, in a sense, surprising. She joins in, in the final part of the Marschallin's first phrase, just upon the critical word “andern” (“other”). Her intervention creates a sudden brief dissonance (a minor-second chord), which immediately disappears when the two womem (who are both in love with Octavian) harmonically conclude the phrase at a distance of a minor-third. What Sophie perceives is a strange religious atmosphere that she cannot really understand, since she is not aware of the <italic>liason</italic> between Octavian and the Marschallin. The <italic>incipit</italic> of the main theme (the characteristic imprinting of the whole trio) is then immediately transposed to a different key (from <italic>D</italic> flat major to <italic>A</italic> major) by Octavian, whose initial attitude seems to be mainly dominated by embarassing doubts and questions. But finally the reasons of love prevail over all doubts. At the end of the trio, while the two young lovers sing an expected “dich habe ich lieb” (“I love you”), the Marschallin concludes with an enigmatic phrase:</p><disp-quote><p><italic>als wie halt Männer das glücklich sein verstehen</italic><xref ref-type="fn" rid="fn0017"><sup>17</sup></xref>.</p></disp-quote><p>singing the last note alone over a perfect tonic chord.</p><p>The three examples of polyphonic constructions, created by Beethoven, Verdi, and Strauss, are all characterized by strong unitary conceptions, based on complex parallel networks of harmonic, melodic, timbric, and semantic relationships (which have been extensively analyzed in musicological literature<xref ref-type="fn" rid="fn0018"><sup>18</sup></xref>). At the same time, one can easily recognize some significant differences that distinguish the three cases, both from the musical and from the semantic point of view. The structure of Fidelio's quartet is very close to a <italic>canon-form</italic>, where the entrance of each voice is associated to a specific semantic connotation. Rigoletto's quartet is, instead, dominated by strong musical contrasts that reflect the conflicting feelings of four human beings, living in a highly dramatic situation. Finally, Strauss' trio seems to propose a kind of musical and semantic “peaceful resolution.” The trio is perceived by the listener as a strongly unitary musical idea that evolves in time. The three female voices are in a sense “entangled,” sometimes creating the illusion that a single voice is singing (as happens in the case of some entangled quantum objects, whose parts are indistinguishable). Such musical situations can be naturally represented in the framework of the quantum musical semantics, where <italic>musical thoughts</italic> are dealt with as holistic ideal objects that vaguely allude to a (possibly infinite) variety of co-existing ideas.</p><p>The analysis proposed in this article has concerned questions that belong to worlds apparently “far apart”: the theory of quantum computers, psychology, logical semantics, and music. A common pattern that arises in all these fields is a frequent and sometimes essential emergence of some characteristic parallel structures. We have seen how the quantum-theoretic concepts of <italic>superposition</italic> and <italic>entanglement</italic> have inspired the development of a “bridge-theory” (based on the quantum computational semantics) that can be usefully applied to a formal representation of different kinds of phenomena where parallelism plays a relevant role.</p><sec><title>Conflict of interest statement</title><p>The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.</p></sec></sec></body><back><ack><p>GS's work has been supported by the Italian Ministry of Scientific Research within the FIRB project “Structures and Dynamics of Knowledge and Cognition,” Cagliari Unit F21J12000140001; RL's work has been supported by the Italian Ministry of Scientific Research within the PRIN project “Automata and Formal Languages: Mathematical Aspects and Applications.”</p></ack><fn-group><fn id="fn0001"><p><sup>1</sup>See, for instance, Penrose (<xref rid="B14" ref-type="bibr">1994</xref>).</p></fn><fn id="fn0002"><p><sup>2</sup>See, for instance, Fouché et al. (<xref rid="B11" ref-type="bibr">2007</xref>).</p></fn><fn id="fn0003"><p><sup>3</sup>See, for instance, Savage (<xref rid="B17" ref-type="bibr">1998</xref>) and Gudder (<xref rid="B12" ref-type="bibr">1999</xref>).</p></fn><fn id="fn0004"><p><sup>4</sup>Some basic intuitive ideas of the quantum computational semantics are close to the “quantum cognition approach” that has been extensively developed in recent times (see, for instance, Aerts and Gabora, <xref rid="B1" ref-type="bibr">2005a</xref>,<xref rid="B2" ref-type="bibr">b</xref>; Aerts and Sozzo, <xref rid="B3" ref-type="bibr">2014</xref>). In both theories <italic>concepts</italic> and <italic>thoughts</italic> are represented as special abstract entities that can be described in the framework of the quantum-theoretic formalism. The technical developments of the two approaches are, however, different.</p></fn><fn id="fn0005"><p><sup>5</sup>A survey of quantum computation theory can be found, for instance, in Nielsen and Chuang (<xref rid="B13" ref-type="bibr">2000</xref>).</p></fn><fn id="fn0006"><p><sup>6</sup>The basic property of the tensor product <inline-formula><mml:math id="M116"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> ⊗ <inline-formula><mml:math id="M117"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub> of two (finite-dimensional) Hilbert spaces <inline-formula><mml:math id="M118"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> and <inline-formula><mml:math id="M119"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub> is the following: <inline-formula><mml:math id="M120"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> ⊗ <inline-formula><mml:math id="M121"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub> is a Hilbert space that properly includes an isomorphic image of the Cartesian product <inline-formula><mml:math id="M122"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> × <inline-formula><mml:math id="M123"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub> (consisting of all ordered pairs of vectors that belong to the spaces <inline-formula><mml:math id="M124"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> and <inline-formula><mml:math id="M125"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub>, respectively). Furthermore, <inline-formula><mml:math id="M126"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> ⊗ <inline-formula><mml:math id="M127"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub> contains all possible superpositions of its elements. A vector |ψ〉 of <inline-formula><mml:math id="M128"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> ⊗ <inline-formula><mml:math id="M129"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub> is called <italic>factorized</italic> iff |ψ〉 corresponds to a pair (|ψ<sub>1</sub>〉, |ψ<sub>2</sub>〉)∈<inline-formula><mml:math id="M130"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> × <inline-formula><mml:math id="M131"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub>. In such a case, it is customary to write: |ψ〉 = |ψ<sub>1</sub>〉 ⊗ |ψ<sub>2</sub>〉. Of course, not all vectors of <inline-formula><mml:math id="M132"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>1</sub> ⊗ <inline-formula><mml:math id="M133"><mml:mi mathvariant="-tex-caligraphic">H</mml:mi></mml:math></inline-formula><sub>2</sub> are factorized.</p></fn><fn id="fn0007"><p><sup>7</sup>As is well-known, the literature devoted to the study of parallel structures in the mind/brain-behavior is very rich. As an example, one can refer to some important contributions of Damasio (see, for instance, Damasio, <xref rid="B10" ref-type="bibr">1999</xref>).</p></fn><fn id="fn0008"><p><sup>8</sup>See (Dalla Chiara et al., <xref rid="B7" ref-type="bibr">2005</xref>, <xref rid="B6" ref-type="bibr">2010</xref>, <xref rid="B8" ref-type="bibr">in press</xref>).</p></fn><fn id="fn0009"><p><sup>9</sup>See (Dalla Chiara et al., <xref rid="B9" ref-type="bibr">2012</xref>).</p></fn><fn id="fn0010"><p><sup>10</sup><italic>Fairest daughter of love, I am a slave of your charms; with but a single word you could relieve my every pain. Come touch my breast and feel how my heart is racing. With but a single word you could relieve my every pain</italic>.</p></fn><fn id="fn0011"><p><sup>11</sup><italic>Ah! Ah! That really makes me laugh, talk like that is cheap enough</italic>.</p></fn><fn id="fn0012"><p><sup>12</sup><italic>Ah, these are the loving words the scoundrel spoke once to me! O wretched heart betrayed, do not break of sorrow</italic>.</p></fn><fn id="fn0013"><p><sup>13</sup><italic>But how can it be that I was the little Resi and that I shall be the old lady. .… How can it come to pass? How can God decree it so? While, in fact, I am always the same. And if indeed it must be so, why does he let me look at it so clearly? Why does he not hide it to me? All this is a mystery, a great mystery</italic>.</p></fn><fn id="fn0014"><p><sup>14</sup>The term “genidentity,” which refers to the problematic <italic>identity of individuals through time</italic> has been introduced by Lewin (in his doctoral thesis in 1922) and has been further investigated by Reichenbach and many other scholars. See, for instance, Reichenbach (<xref rid="B16" ref-type="bibr">1928</xref>).</p></fn><fn id="fn0015"><p><sup>15</sup><italic>I promised to love him in the right way, even to love his love for another woman</italic>.</p></fn><fn id="fn0016"><p><sup>16</sup><italic>Tell the beautiful and pure girl</italic>.</p></fn><fn id="fn0017"><p><sup>17</sup><italic>as far as men can understand happiness</italic>.</p></fn><fn id="fn0018"><p><sup>18</sup>See, for instance, Budden (<xref rid="B5" ref-type="bibr">1983</xref>), Solomon (<xref rid="B18" ref-type="bibr">1998</xref>), Principe (<xref rid="B15" ref-type="bibr">2004</xref>).</p></fn></fn-group><ref-list><title>References</title><ref id="B1"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Aerts</surname><given-names>D.</given-names></name><name><surname>Gabora</surname><given-names>L.</given-names></name></person-group> (<year>2005a</year>). <article-title>A theory of concepts and their combinations I: the structure of the sets of contexts and properties</article-title>. <source>Kybernetics</source><volume>34</volume>, <fpage>167</fpage>–<lpage>191</lpage>. <pub-id pub-id-type="doi">10.1108/03684920510575799</pub-id></mixed-citation></ref><ref id="B2"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Aerts</surname><given-names>D.</given-names></name><name><surname>Gabora</surname><given-names>L.</given-names></name></person-group> (<year>2005b</year>). <article-title>A theory of concepts and their combinations II: a Hilbert space representation</article-title>. <source>Kybernetics</source><volume>34</volume>, <fpage>192</fpage>–<lpage>221</lpage>. <pub-id pub-id-type="doi">10.1108/03684920510575807</pub-id></mixed-citation></ref><ref id="B3"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Aerts</surname><given-names>D.</given-names></name><name><surname>Sozzo</surname><given-names>S.</given-names></name></person-group> (<year>2014</year>). <article-title>Quantum entanglement in conceptual combinations</article-title>. <source>Int. J. Theor. Phys.</source><volume>53</volume>, <fpage>3587</fpage>–<lpage>3603</lpage>. <pub-id pub-id-type="doi">10.1007/s10773-013-1946-z</pub-id></mixed-citation></ref><ref id="B4"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Boncinelli</surname><given-names>E.</given-names></name></person-group> (<year>2012</year>). <source>Mi Ritorno in Mente. Il Corpo, le Emozioni, la Coscienza</source>. <publisher-loc>Milano</publisher-loc>: <publisher-name>Longanesi</publisher-name>.</mixed-citation></ref><ref id="B5"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Budden</surname><given-names>J.</given-names></name></person-group> (<year>1983</year>). <source>The Operas of Verdi</source>. <publisher-loc>New York, NY</publisher-loc>: <publisher-name>Oxford University Press</publisher-name>.</mixed-citation></ref><ref id="B6"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Dalla Chiara</surname><given-names>M. L.</given-names></name><name><surname>Giuntini</surname><given-names>R.</given-names></name><name><surname>Ledda</surname><given-names>A.</given-names></name><name><surname>Leporini</surname><given-names>R.</given-names></name><name><surname>Sergioli</surname><given-names>G.</given-names></name></person-group> (<year>2010</year>). <article-title>Entanglement as a semantic resource</article-title>. <source>Found. Phys.</source><volume>40</volume>, <fpage>1494</fpage>–<lpage>1518</lpage>. <pub-id pub-id-type="doi">10.1007/s10701-010-9407-5</pub-id></mixed-citation></ref><ref id="B7"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Dalla Chiara</surname><given-names>M. L.</given-names></name><name><surname>Giuntini</surname><given-names>R.</given-names></name><name><surname>Leporini</surname><given-names>R.</given-names></name></person-group> (<year>2005</year>). <article-title>Logics from quantum computation</article-title>. <source>Int. J. Quantum Inf.</source><volume>3</volume>, <fpage>293</fpage>–<lpage>337</lpage>. <pub-id pub-id-type="doi">10.1142/S0219749905000943</pub-id></mixed-citation></ref><ref id="B8"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Dalla Chiara</surname><given-names>M. L.</given-names></name><name><surname>Giuntini</surname><given-names>R.</given-names></name><name><surname>Leporini</surname><given-names>R.</given-names></name><name><surname>Sergioli</surname><given-names>G.</given-names></name></person-group> (<year>in press</year>). <article-title>Holistic logical arguments in quantum computation</article-title>. <source>Math. Slov.</source></mixed-citation></ref><ref id="B9"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Dalla Chiara</surname><given-names>M. L.</given-names></name><name><surname>Giuntini</surname><given-names>R.</given-names></name><name><surname>Luciani</surname><given-names>A. R.</given-names></name><name><surname>Negri</surname><given-names>E.</given-names></name></person-group> (<year>2012</year>). <source>From Quantum Information to Musical Semantics</source>. Illustrated by C. Seravalli. <publisher-loc>London</publisher-loc>: <publisher-name>College Publications</publisher-name>.</mixed-citation></ref><ref id="B10"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Damasio</surname><given-names>A. R.</given-names></name></person-group> (<year>1999</year>). <source>The Feeling of What Happens: Body and Emotions in Making of Consciousness</source>. <publisher-loc>New York, NY</publisher-loc>: <publisher-name>Harcourt Brace & Company</publisher-name>.</mixed-citation></ref><ref id="B11"><mixed-citation publication-type="webpage"><person-group person-group-type="author"><name><surname>Fouché</surname><given-names>W.</given-names></name><name><surname>Heidema</surname><given-names>J.</given-names></name><name><surname>Jones</surname><given-names>G.</given-names></name><name><surname>Potgieter</surname><given-names>P. H.</given-names></name></person-group> (<year>2007</year>). <source>Deutsch's universal quantum Turing machine (Revisited).</source> arXiv:quant-ph/0701108. Available online at: <ext-link ext-link-type="uri" xlink:href="http://arxiv.org/pdf/quant-ph/0701108v1.pdf">http://arxiv.org/pdf/quant-ph/0701108v1.pdf</ext-link></mixed-citation></ref><ref id="B12"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Gudder</surname><given-names>S.</given-names></name></person-group> (<year>1999</year>). <article-title>Quantum automata: an overview</article-title>. <source>Int. J. Theor. Phys.</source><volume>38</volume>, <fpage>2261</fpage>–<lpage>2282</lpage>. <pub-id pub-id-type="doi">10.1023/A:1026663432352</pub-id></mixed-citation></ref><ref id="B13"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Nielsen</surname><given-names>M. A.</given-names></name><name><surname>Chuang</surname><given-names>I. L.</given-names></name></person-group> (<year>2000</year>). <source>Quantum Computation and Quantum Information</source>. <publisher-loc>New York, NY</publisher-loc>: <publisher-name>Cambridge University Press</publisher-name>.</mixed-citation></ref><ref id="B14"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Penrose</surname><given-names>R.</given-names></name></person-group> (<year>1994</year>). <source>Shadows of the Mind.</source><publisher-loc>Oxford</publisher-loc>: <publisher-name>Oxford University Press</publisher-name>.</mixed-citation></ref><ref id="B15"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Principe</surname><given-names>Q.</given-names></name></person-group> (<year>2004</year>). <source>Strauss. La Musica Nello Specchio di Eros.</source><publisher-loc>Milano</publisher-loc>: <publisher-name>Bompiani</publisher-name>.</mixed-citation></ref><ref id="B16"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Reichenbach</surname><given-names>H.</given-names></name></person-group> (<year>1928</year>). <source>Philosophie der Raum-Zeit-Lehre.</source><publisher-loc>Berlin-Leipzig</publisher-loc>: <publisher-name>De Gruyter</publisher-name>.</mixed-citation></ref><ref id="B17"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Savage</surname><given-names>J. E.</given-names></name></person-group> (<year>1998</year>). <source>Models Of Computation: Exploring the Power of Computing.</source><publisher-loc>Reading</publisher-loc>: <publisher-name>Addison Wesley</publisher-name>.</mixed-citation></ref><ref id="B18"><mixed-citation publication-type="book"><person-group person-group-type="author"><name><surname>Solomon</surname><given-names>M.</given-names></name></person-group> (<year>1998</year>). <source>Beethoven.</source><publisher-loc>London</publisher-loc>: <publisher-name>Schirmer Trade Books</publisher-name>.</mixed-citation></ref></ref-list></back></pmc></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/OperaV1/Data/Pmc/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000023 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Curation/biblio.hfd -nk 000023 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Musique
|area= OperaV1
|flux= Pmc
|étape= Curation
|type= RBID
|clé= PMC:4612715
|texte= Quantum information, cognition, and music
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Curation/RBID.i -Sk "pubmed:26539139" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Curation/biblio.hfd \
| NlmPubMed2Wicri -a OperaV1
| This area was generated with Dilib version V0.6.21. |  |