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
[if-you-see-this-DO-NOT-CLICK]
galvao_ubc_july_2010.pdf [ 2.22MB ]
[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ão Raphael Dias da Silva Instituto de Física – Universidade Federal Fluminense (Brazil)  Elham Kashefi School of Informatics, Univ. of Edinburgh  QAMF Workshop – UBC – July 24th 2010  arXiv:1003.4971v1 [quant-ph]  Outline  •  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 •  Conclusion  Time 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: Trip back in time = CTC  Entrance  V time  Exit  V = interaction region between you (past) and you (future)  Time travel - CTCs •  Time travel scenario: Trip back in time = CTC  Entrance  U •  Equivalent alternative:  V = interaction region between you (past) and you (future)  Exit  time CTC  Entrance  U  U = interaction region Exit  Deutsch’s model for CTCs Deutsch, Phys. Rev. D 44, 3197 (1991)  •  U = 2-qubit unitary -  1 qubit travels back in time -  1 qubit doesn’t  U  •  Initial state:
 ρCTC ⊗ ρ in •  After U:
 U( ρCTC ⊗ ρ in )U + € •  Self-consistency condition:  ρCTC = TrB [U( ρ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 CTCs •  Some characteristics: -  avoids paradoxes; -  Under-determination of multiple  solutions/maps: maxent? wormhole initial conditions? …  Deutsch, Phys. Rev. D 44, 3197 (1991)  U  •  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 1  0 = CTR − Z =  0  0  J−θ  € 1   ρ in = (1+ n ⋅ σ ) 2  1   ρCTC = (1+ m ⋅ σ ) € 2  0 1 0 0  0 0  0 0 1 0  0 −1  −iθ 1 1 e  J−θ =   2 1 −e−iθ   1   ρ out€= (1+ r ⋅ σ ) 2  •  Self-consistency: €  €  €    ρCTC : m = (n z ,0,0) •  Solution for generic input:
   2 ρ : r  out = (n z ,0,0)  •  Alternative solution for €  ψ in  Non-linear map!   1 iθ ρ = ρ : m = (0,0,mz ) : = 0 + e 1 ) CTC ( out 2  Testing Deutsch’s model  U  •  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.  The one-way model of quantum computing •  Proposed by Raussendorf/Briegel [PRL 86, 5188 (2001)]  •  Consists in:  Credit: Robert Raussendorf  -  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 measurements  Example: J gate + ≡ 1/ 2 ( 0 + 1 )  ψ in = α 0 + β 1  ψ in ψ out €  iθ  0 + e 1 ↔ outcome s1 = 0    Θ M = Meas. on basis   iθ   0 − e 1 ↔ outcome s1 = 1    •  Simple calculation shows that
 ψ out = J−θ ψ in € •   € Circuit can be represented as command sequence:  X 2s1 M1θ G , €  G ≡ CTRZ ψ in  1  ⊗ +  2  •  Equivalent circuit – measure Z, implement CTR-X (CNOT) coherently: ψ in  €  ψ out € €  J gate in MBQC = CTC ψ in  ⇔  ψ out  €  •  Stabilizers of state €  s1  G  :  X 2s1 M1θ G , G ≡ CTRZ ψ in  1  ⊗ +  (Z1 ⊗ X 2 ) 0 = Z10 ⊗ X 20 = 1 (identity)  1 1 1 (Z1 ⊗ X 2 ) = Z1 ⊗ X 2  s1  €independently of the outcome s1 of the That is, Z1 ⊗ X 2 is stabilizer measurement on qubit 1:  € €  €  €  Z1s1 ⊗ X 2s1 G = G  •  We can then perform stabilizer manipulation:  X 2s1 M1θ G = X 2s1 M1θ (Z1s1 X 2s1 G ) €  = X 2s1+ s1 M1θ Z1s1 G = M1θ Z1s1 G Time-travel situation: we need to apply Z depending on outcome of measurement not yet made.  €  2  J gate in MBQC = CTC •  Putting this CTC in Deutsch format: θ 1  ⇔  s1 1  M Z G  €  €  ⇔  MZ  €  €  €  ⇔  ψ in  Z  J−Θ  ψ out  +  €  €  €  CTC  € €  MZ  ψ out €  €  ⇔  MZ  Comparing the one-way model with Deutsch: Deutsch:  1  1+ n z ρ in =  2  n x + in y €   ψ in    ρ in : n = (n x ,n y ,n z )    ρ anc : m = (n z2 ,0,0)   ρ = ρ : r = (n z ,0,0) CTC  out n x − in y   1− n z   One-way model:  €  ψ out  →ρ  out  1 1 =  2  nz  €  ψ in€= α 0 + β 1 ψ out = J−θ ψ in = α + + βe−iθ −  €  €  Deutsch’s € prediction is different from the one based on the one-way€model. What’s wrong with Deutsch?  nz   1  CTCs: 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 ≡  CTC  1 00 + 11 ) ( 2  Simulation using teleportation and post-selection: B’=C  €  •  We post-select projections onto 
β 00 -  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?  BSS x MBQC  M  Z  ⇒  ancillaout  ψ out CTC we studied  €  ψ out  Its 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.  ancillaout  ψ out  •  Some BSS circuits reduce to MBQC patterns that deterministically simulate a unitary. - flow, gflow theorems.  € €  ψ in  •  For example, the BSS circuit above is equivalent to:  ψ out €  ψ in  •  Or more simply:  €  J−Θ €ψ out  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.2219v1  PP versus PSPACE From http://qwiki.stanford.edu/wiki/Complexity_Zoo  PP  Like 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 accept  PSPACE  Whereas 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.  How 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 model  From Bennett’s talk (2005).  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
United States 11 0
Germany 3 1
Chile 1 0
Canada 1 0
Czech Republic 1 0
France 1 0
China 1 12
City Views Downloads
Ashburn 7 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