- 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 2010
Page Metadata
Item Metadata
Title | Closed time-like curves in measurement-based quantum computation |
Creator |
Galvao, Ernesto Fagundes |
Date Created | 2010-11-22 |
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 |
Collection |
Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics |
Date Available | 2010-11-22 |
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 |
Digital Resource Original Record | https://open.library.ubc.ca/collections/29986/items/1.0103156/source |
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: