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).
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics /
- Closed time-like curves in measurement-based quantum...
Open Collections
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
Page Metadata
Item Metadata
Title | Closed time-like curves in measurement-based quantum computation |
Creator |
Galvao, Ernesto Fagundes |
Contributor | University of British Columbia. Department of Physics and Astronomy Pacific Institute for the Mathematical Sciences. Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics |
Date Issued | 2010-07-24 |
Description | Many results have been recently obtained regarding the power of hypothetical closed time-like curves (CTC’s) in quantum computation. Most of them have been derived using Deutsch’s influential model for quantum CTCs [D. Deutsch, Phys. Rev. D 44, 3197 (1991)]. Deutsch’s model demands self-consistency for the time-travelling system, but in the absence of (hypothetical) physical CTCs, it cannot be tested experimentally. In this paper we show how the one-way model of measurement-based quantum computation (MBQC) can be used to test Deutsch’s model for CTCs. Using the stabilizer formalism, we identify predictions that MBQC makes about a specific class of CTCs involving travel in time of quantum systems. Using a simple example we show that Deutsch’s formalism leads to predictions conflicting with those of the one-way model. There exists an alternative, little-discussed model for quantum time-travel due to Bennett and Schumacher (in unpublished work, see http://bit.ly/cjWUT2), which was rediscovered recently by Svetlichny [arXiv:0902.4898v1]. This model uses quantum teleportation to simulate (probabilistically) what would happen if one sends quantum states back in time. We show how the Bennett/ Schumacher/ Svetlichny (BSS) model for CTCs fits in naturally within the formalism of MBQC. We identify a class of CTC’s in this model that can be simulated deterministically using techniques associated with the stabilizer formalism. We also identify the fundamental limitation of Deutsch's model that accounts for its conflict with the predictions of MBQC and the BSS model. This work was done in collaboration with Raphael Dias da Silva and Elham Kashefi, and has appeared in preprint format (see website). |
Subject |
closed time-like curves quantum computation one-way model |
Type |
Moving Image Other |
Language | eng |
Date Available | 2010-11-22 |
Provider | Vancouver : University of British Columbia Library |
DOI | 10.14288/1.0103156 |
URI | http://hdl.handle.net/2429/30070 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Faculty |
Aggregated Source Repository | DSpace |
Download
- Media
- [if-you-see-this-DO-NOT-CLICK]
- galvao_ubc_july_2010.pdf [ 2.22MB ]
- WS Jul 24 Galvao.mp4 [ 106MB ]
- 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
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 1 | 0 |
City | Views | Downloads |
---|---|---|
Ashburn | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
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>
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.59373.1-0103156/manifest