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

Closed time-like curves in measurement-based quantum computation 2010

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

Item Metadata

Download

Media
galvao_ubc_july_2010.pdf
galvao_ubc_july_2010.pdf [ 2.22MB ]
WS Jul 24 Galvao.mp4 [ 106MB ]
WS Jul 24 Galvao.mp4
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
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) 
 arXiv:1003.4971v1 [quant-ph] Elham Kashefi School of Informatics, Univ. of Edinburgh QAMF Workshop – UBC – July 24th 2010 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: V Entrance Exit Trip back in time = CTC V = interaction region between you (past) and you (future) time Time travel - CTCs •  Time travel scenario: U Entrance Exit Trip back in time = CTC V = interaction region between you (past) and you (future) time U Entrance
 Exit •  Equivalent alternative: CTC U = interaction region Deutsch’s model for CTCs U •  U = 2-qubit unitary -  1 qubit travels back in time -  1 qubit doesn’t Deutsch, Phys. Rev. D 44, 3197 (1991) •  Initial state: •  After U: •  Self-consistency condition:
€ ρCTC ⊗ ρin € U(ρCTC ⊗ ρin )U + € ρ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 U •  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−θ = 1 2 1 e− iθ 1 −e− iθ       € = CTR − Z = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 −1             •  Self-consistency:  € ρin = 1 2 (1+  n ⋅  σ )  € ρCTC = 1 2 (1+  m ⋅  σ )  € ρout = 1 2 (1+  r ⋅  σ ) •  Solution for generic input: •  Alternative solution for                                 : € ψin = 1 2 0 + e iθ 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. U The 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 measurements Credit: Robert Raussendorf Example:  J gate •  Simple calculation shows that •  Circuit can be represented as command sequence:
€ ψin =α 0 + β 1          + ≡1/ 2 0 + 1( ) MΘ =  Meas. on basis 0 + e iθ 1 ↔  outcome s1 = 0 0 − eiθ 1 ↔  outcome s1 =1           € ψin € ψout € ψout = J−θ ψin € ψin € ψout € X2s1M1θ G ,           G ≡ CTRZ ψ in 1 ⊗ + 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 ψin 1 ⊗ + 2 •  We can then perform stabilizer manipulation:
€ G € (Z1 ⊗ X2)0 = Z10 ⊗ X20 =1 (identity) (Z1 ⊗ X2)1 = Z11 ⊗ X21    € Z1s1 ⊗ X2s1 € Z1s1 ⊗ X2s1 G = G € X2s1M1θ G = X2s1M1θ (Z1s1X2s1 G ) = X2s1+s1M1θZ1s1 G = M1θZ1s1 G Time-travel situation: we need to apply Z depending on outcome of measurement not yet made. € ⇔ € ψin € + € J−Θ € MZ € Z € ψout € M1θZ1s1 G € ⇔ € ⇔ € MZ € ⇔ •  Putting this CTC in Deutsch format:  J gate in MBQC = CTC € ψout € MZ CTC Comparing the one-way model with Deutsch:  €  Deutsch:  € ρin :  n = (nx,ny,nz ) ρanc :  m = (nz2,0,0) ρout = ρCTC :  r = (nz,0,0)      One-way model: € ψin =α 0 + β 1 ψout = J−θ ψin =α + + βe− iθ − € ρin = 1 2 1+ nz nx − iny nx + iny 1− nz       € ρout = 1 2 1 nz nz 1       € → Deutsch’s prediction is different from the one based on the one-way model.  What’s wrong with Deutsch? € ψin € ψout 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 ≡ 1 2 00 + 11( ) CTC
 Simulation 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? € β00 BSS x MBQC € ψout € MZ CTC we studied € ψout € ancillaout 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. •  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.2219v1 PP versus PSPACE 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 From http://qwiki.stanford.edu/wiki/Complexity_Zoo PP 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. PSPACE 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 3 0
Germany 2 0
France 1 0
Chile 1 0
Czech Republic 1 0
China 1 10
City Views Downloads
Unknown 3 0
Mountain View 2 0
Beijing 1 0
Kladno 1 0
Concepción 1 0
Ashburn 1 0

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

Share

Share to:

Comment

Related Items