Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics

Closed time-like curves in measurement-based quantum computation Galvao, Ernesto Fagundes 2010-07-24

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata


galvao_ubc_july_2010.pdf [ 2.22MB ]
WS Jul 24 Galvao.mp4 [ 106MB ]
JSON: 1.0103156.json
JSON-LD: 1.0103156+ld.json
RDF/XML (Pretty): 1.0103156.xml
RDF/JSON: 1.0103156+rdf.json
Turtle: 1.0103156+rdf-turtle.txt
N-Triples: 1.0103156+rdf-ntriples.txt
Original Record: 1.0103156 +original-record.json
Full Text

Full Text

Closed timelike curves in !measurement-based quantum computation!Ernesto F. GalvãoRaphael Dias da SilvaInstituto de Física – Universidade Federal Fluminense (Brazil) arXiv:1003.4971v1 [quant-ph]Elham KashefiSchool of Informatics, Univ. of EdinburghQAMF Workshop – UBC – July 24th 2010Outline•  Closed time-like curves (CTCs) = time travel•  Deutsch’s model for CTCs•  How CTCs show up in measurement-based quantum computation•  CTC model by Bennett/Schumacher/Svetlichny•  ConclusionTime travel•  To the future? Easy, use relativity.•  To the past? More involved:- Relativity predicts solutions with closed timelike curves (CTCs)= travel to the past- It’s not known whether CTCs are physically possible, perhaps with clever black-hole engineering.- To avoid paradoxes, self-consistency conditions on time-travellers must apply – more on that later.Time travel - CTCs•  Time travel scenario:VEntranceExitTrip back in time = CTCV = interaction region between you (past) and you (future)timeTime travel - CTCs•  Time travel scenario:UEntranceExitTrip back in time = CTCV = interaction region between you (past) and you (future)timeUEntrance Exit•  Equivalent alternative:CTCU = interaction regionDeutsch’s model for CTCsU•  U = 2-qubit unitary-  1 qubit travels back in time-  1 qubit doesn’tDeutsch, Phys. Rev. D 44, 3197 (1991)•  Initial state:•  After U:•  Self-consistency condition:€ ρCTC⊗ρin€ U(ρCTC⊗ρin)U+€ ρCTC=TrBU(ρCTC⊗ρin)U+[ ]•  Deutsch showed that:-    there’s always at least 1 self-consistent solution; -  there can be multiple such solutions;-  each solution corresponds to an input-output map, in general non-linear.Deutsch’s model for CTCsU•  Some characteristics:-  avoids paradoxes;-  Under-determination of multiple solutions/maps: maxent? wormhole initial conditions? …Deutsch, Phys. Rev. D 44, 3197 (1991)•  Computational power of Deutsch’s CTCs :Non-orthogonal state discrimination? Solution to NP-complete problems?-  Bacon arXiv:quant-ph/0309189v3 (solves NP-complete problems)-  Brun et al. arXiv:0811.1209v2 (non-orthogonal state discrimination)-  Aaronson, Watrous: arXiv:0808.2669v1 (CTCs -> PSPACE)-  Bennett et al. arXiv:0908.3023v2 (criticism to results above)-  Cavalcanti, Menicucci arXiv:1004.1219v2 (criticism of the criticism…)Deutsch - example€ J−θ=121e−iθ1−e−iθ      € =CTR−Z=100001000010000−1            •  Self-consistency:  € ρin=12(1+ n ⋅ σ )  € ρCTC=12(1+ m ⋅ σ )  € ρout=12(1+ r ⋅ σ )•  Solution for generic input:•  Alternative solution for                                 :€ ψin=120+eiθ1( )  € ρCTC=ρout: m =(0,0,mz)  € ρCTC: m =(nz,0,0)ρout: r =(nz2,0,0)   Non-linear map!€ J−θTesting Deutsch’s model•  Discussion of computational power of CTCs uses Deutsch’s model. In the absence of experiments, how to check if the model is sound? •  We’ll see that measurement-based quantum computation offers an answer.UThe one-way model of quantum computing•  Proposed by Raussendorf/Briegel                       [PRL 86, 5188 (2001)]•  Consists in:-  Preparation of standard entangled states via Heisenberg interactions – cluster states; -  Adaptive sequence of 1-qubit measurements.•   Computational resource = quantum correlations of initial state•  Algorithm = choice of adaptive sequence of measurementsCredit: Robert RaussendorfExample:  J gate•  Simple calculation shows that•  Circuit can be represented as command sequence:€ ψin=α0+β1         +≡1/20+1( ) MΘ= Meas. on basis 0+eiθ1↔ outcome s1=00−eiθ1↔ outcome s1=1       € ψin€ ψout€ ψout=J−θψin€ ψin€ ψout€ X2s1M1θG,          G≡CTRZψin1⊗+2•  Equivalent circuit – measure Z, implement CTR-X (CNOT) coherently: J gate in MBQC = CTC•  Stabilizers of state            :That is,                    is stabilizer independently of the outcome s1 of the measurement on qubit 1:€ ψin€ ψout€ ⇔€ X2s1M1θG,G≡CTRZψin1⊗+2•  We can then perform stabilizer manipulation: G€ (Z1⊗X2)0=Z10⊗X20=1 (identity)(Z1⊗X2)1=Z11⊗X21   € Z1s1⊗X2s1€ Z1s1⊗X2s1G=G€ X2s1M1θG=X2s1M1θ(Z1s1X2s1G)=X2s1+s1M1θZ1s1G=M1θZ1s1GTime-travel situation: we need to apply Z depending on outcome of measurement not yet made. € ⇔€ ψin€ +€ J−Θ€ MZ€ Z€ ψout€ M1θZ1s1G€ ⇔€ ⇔€ MZ€ ⇔•  Putting this CTC in Deutsch format: J gate in MBQC = CTC€ ψout€ MZCTCComparing the one-way model with Deutsch:  € Deutsch:  € ρin: n =(nx,ny,nz)ρanc: m =(nz2,0,)ρout=ρCTC: r =(nz,0,)     One-way model:€ ψin=α0+β1ψout=J−θψin=α++βe−iθ−€ ρin=121+nznx−inynx+iny1−nz      € ρout=121nznz1      € →Deutsch’s prediction is different from the one based on the one-way model.  What’s wrong with Deutsch?€ ψin€ ψoutCTCs: model by Bennett/Schumacher/Svetlichny (BSS)•  Bennett and Schumacher, unpublished (2002) – see seminar•  Rediscovered independently by Svetlichny (2009) - arXiv:0902.4898v1- Related work on black holes by Horowitz/Maldacena (2004), Preskill/Gottesman (2004) € β00≡1200+11( )CTCSimulation using teleportation and post-selection: B’=C•  We post-select projections onto -  Postselection successful: state B’ is teleported back in time (state C = state B’)-  Simulation works only when post-selection happens -> finite probability of success. What are BSS’s predictions for our CTC?€ β00BSS x MBQC€ ψout€ MZCTC we studied€ ψout€ ancillaoutIts BSS simulation circuit€ ⇒•  Simple calculation shows that BSS circuit implements (probabilistically) the map€ ψin→ψout=J−θψin… recovering exactly MBQC’s prediction!BSS is the right model to explain CTCs in MBQC, and not Deutsch’s…Deutsch/BSS comparison-  Deutsch’s self-consistency is achieved with artificial mixed-states, CTC qubit sent back in time decorrelated with other systems.-  BSS preserves entanglement and correlations of CTC qubit due to teleportation step.-  Deutsch solutions with pure-state CTC qubit coincide with BSS solution.MBQC as deterministic simulations of CTCs•  Stabilizer techniques enable us to simplify BSS circuits-  Z deletion;-  Local complementation. •  Some BSS circuits reduce to MBQC patterns that deterministically simulate a unitary.- flow, gflow theorems.•  For example, the BSS circuit above is equivalent to:•  Or more simply:€ ψout€ ancillaout€ ψin€ ψout€ ψin€ ψout€ J−ΘConclusions•  CTCs appear in MBQC; we analyze them using two CTC models. •  BSS’s model  agrees with MBQC. •  Deutsch’s model is in conflict with MBQC – the CTC qubit is sent to past stripped of its entanglement.•  We characterize a class of CTCs that admit deterministic simulation circuits using the BSS model. •  More work is needed to better understand implications of the BSS model:-  MQ + Deutsch’s CTCs = PSPACE (Aaronson/Watrous 2008)-  BSS is associated with complexity class PostBQP=PP (Aaronson 2004)-  See recent work (and experiment) by Lloyd et al. : arXiv:1005.2219v1PP versus PSPACELike BPP, PP is a class defined in an attempt to find out what randomness allows us to do algorithmically. Formally, PP is the class of problems solvable by an NP machine such that, given a "yes" instance, strictly more than 1/2 of the computation paths accept, while given a "no" instance, strictly less than 1/2 of the computation paths acceptFrom P is a class of problems that can be solved in a polynomially-bounded amount of time, PSPACE is the class of problems that can be solved by a deterministic Turing machine that uses only a polynomially-bounded amount of space, regardless of how long the computation takes.PSPACEHow BSS deals with the grandfather paradox•  From Bennett’s talk slides:•  Paradoxical combinations of input and unitary result in post-selection with success probability p=0.Bennett’s classical motivation for the BSS modelFrom Bennett’s talk (2005).


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics

Country Views Downloads
United States 1 0
City Views Downloads
Ashburn 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items