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).
- 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
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 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Faculty |
URI | http://hdl.handle.net/2429/30070 |
Aggregated Source Repository | DSpace |
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
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] }]} |
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.29986.1-0103156/manifest