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

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

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

Item Metadata

Download

Media
galvao_ubc_july_2010.pdf [ 2.22MB ]
[if-you-see-this-DO-NOT-CLICK]
[if-you-see-this-DO-NOT-CLICK]
[if-you-see-this-DO-NOT-CLICK]
WS Jul 24 Galvao.mp4 [ 106MB ]
[if-you-see-this-DO-NOT-CLICK]
Metadata
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
1.0103156.txt
Citation
1.0103156.ris

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 http://bit.ly/crs8Lb•  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 http://qwiki.stanford.edu/wiki/Complexity_ZooPPWhereas 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:  http://bit.ly/crs8Lb•  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).

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
United States 9 0
Germany 3 1
Chile 1 0
Canada 1 0
Czech Republic 1 0
France 1 0
China 1 10
City Views Downloads
Ashburn 5 0
Unknown 4 1
Mountain View 2 0
San Francisco 1 0
Ottawa 1 0
Wilmington 1 0
Concepción 1 0
Kladno 1 0
Beijing 1 0

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

Share

Embed

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"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.29986.1-0103156/manifest

Comment

Related Items