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

Correlations in Measurement-Based Quantum Computing and Bell Inequalities 2011

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

Item Metadata

Download

Media
Vancouver Invited Browne.pdf [ 1.21MB ]
Vancouver Invited Browne.pdf
WS Jul 24 Browne.mp4
WS Jul 24 Browne.mp4 [ 149.56MB ]
Metadata
JSON: 1.0103168.json
JSON-LD: 1.0103168+ld.json
RDF/XML (Pretty): 1.0103168.xml
RDF/JSON: 1.0103168+rdf.json
Turtle: 1.0103168+rdf-turtle.txt
N-Triples: 1.0103168+rdf-ntriples.txt
Citation
1.0103168.ris

Full Text

Bell inequalities for (Measurement Based Quantum) Computation Dan Browne Dept. of Physics and Astronomy University College London s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Quantum Foundations (Measurement- Based) Quantum Computation Sunday, 1 August 2010 Measurement-based quantum computation Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. • 1. Create a special multi-qubit entangled state R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. • 1. Create a special multi-qubit entangled state • e.g. A cluster state R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. • 1. Create a special multi-qubit entangled state • e.g. A cluster state • 2.  Then measure qubits individually, in certain (adaptive) bases, and post-process outcomes. R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. • 1. Create a special multi-qubit entangled state • e.g. A cluster state • 2.  Then measure qubits individually, in certain (adaptive) bases, and post-process outcomes. • Via a suitable choice of measurements, any quantum computation can be acheived. R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation Measure a sub-set of qubits Process measurement results Choose bases for next subset of measurements Computational Output Prepare entangled resource state e.g. cluster state Requires classical “side-computation” Sunday, 1 August 2010 Measurement-based quantum computation +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation • For a cluster state resource it suffices for side-computation to be linear. • Each measurement is of the form and meas. outcomes are relabelled +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation • For a cluster state resource it suffices for side-computation to be linear. • Each measurement is of the form and meas. outcomes are relabelled • The angle      is pre-set and differs for each measurement. +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). θj sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation • For a cluster state resource it suffices for side-computation to be linear. • Each measurement is of the form and meas. outcomes are relabelled • The angle      is pre-set and differs for each measurement. • But bit-value       is calculated on the fly - and set equal to the parity of  a sub-set of previous measurement outcomes. +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). θj sj sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation • For a cluster state resource it suffices for side-computation to be linear. • Each measurement is of the form and meas. outcomes are relabelled • The angle      is pre-set and differs for each measurement. • But bit-value       is calculated on the fly - and set equal to the parity of  a sub-set of previous measurement outcomes. • Final output bits are encoded in the parity of a sub-set of the measurement outcomes. +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). θj sj sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation Measure a sub-set of qubits Process measurement results Choose bases for next subset of measurements Computational Output Prepare entangled resource state e.g. cluster state Requires (linear  / XOR) classical “side-computation” Sunday, 1 August 2010 Bell inequalities Sunday, 1 August 2010 Bell inequalities Sunday, 1 August 2010 Bell inequalities • Bell inequalities (BIs) express restrictions on the joint probability distributions for spatially separated measurements in local hidden variable (LHV) theories. Sunday, 1 August 2010 CHSH inequality Outcome: Setting: s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} • We focus on the parity of the outcomes and define: Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) Sunday, 1 August 2010 CHSH inequality Outcome: Setting: s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} • We focus on the parity of the outcomes and define: • and show that for correlations in any LHV theory: Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 Sunday, 1 August 2010 CHSH inequality • With entangled quantum state,  Alice and Bob can violate this inequality, although not exceeding Tsirelson’s bound: E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 √ 2 Sunday, 1 August 2010 CHSH inequality • With entangled quantum state,  Alice and Bob can violate this inequality, although not exceeding Tsirelson’s bound: • A (loophole-free) demonstration of a Bell Inequality violation would refute local hidden variable theories. E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 √ 2 Sunday, 1 August 2010 CHSH inequality • With entangled quantum state,  Alice and Bob can violate this inequality, although not exceeding Tsirelson’s bound: • A (loophole-free) demonstration of a Bell Inequality violation would refute local hidden variable theories. • The maximal violation (stronger than QM) is achieved by the Popescu-Rohrlich (PR) Box, which acheives E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 √ 2 B. S. Tsirelson, Lett. Math. Phys. (1980). S. Popescu and D. Rohrlich, Found. Phys. (1994) E0,0 + E0,1 + E1,0 − E1,1 = 4 Sunday, 1 August 2010 CHSH inequality • It is useful to re-express the CHSH Inequality directly in terms of conditional probabilities. E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) Sunday, 1 August 2010 CHSH inequality • It is useful to re-express the CHSH Inequality directly in terms of conditional probabilities. • Some simple algebra gives us a very neat representation [1] of the CHSH inequality: E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 1 4 ￿ s1,s2 p(m1 ⊕m2 = s1s2|s1s2) ≤ 34 [1] QIP Folklore: earliest reference I know: Wim Van Dam, PHD Thesis (2000) Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) Sunday, 1 August 2010 CHSH inequality • It is useful to re-express the CHSH Inequality directly in terms of conditional probabilities. • Some simple algebra gives us a very neat representation [1] of the CHSH inequality: • Thus we can phrase the CHSH inequality in terms of a game. E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 1 4 ￿ s1,s2 p(m1 ⊕m2 = s1s2|s1s2) ≤ 34 [1] QIP Folklore: earliest reference I know: Wim Van Dam, PHD Thesis (2000) Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) Sunday, 1 August 2010 CHSH game • Rules: • Alice, Bob are given independent bits s1, s2 from a uniform distribution. • They may not communicate during the game. • Aim: • They should each produce a bit m1, m2, such that • We call games where the desired data is encoded in the XOR of measurement outcomes XOR-games. m1 ⊕m2 = s1s2 m1 XOR m2 = s1 AND s2 Sunday, 1 August 2010 CHSH game 1 4 ￿ s1,s2 p(m1 +m2 = s1s2) ≤ 3 4 ≤ 2 + √ 2 4 ≈ 0.85 LHV Quantum PR Box= 1 Sunday, 1 August 2010 CHSH game • CHSH inequalities bound the mean success probability of the game. 1 4 ￿ s1,s2 p(m1 +m2 = s1s2) ≤ 3 4 ≤ 2 + √ 2 4 ≈ 0.85 LHV Quantum PR Box= 1 Sunday, 1 August 2010 CHSH game • CHSH inequalities bound the mean success probability of the game. • The GHZ paradox can also be related to a very similar game. 1 4 ￿ s1,s2 p(m1 +m2 = s1s2) ≤ 3 4 ≤ 2 + √ 2 4 ≈ 0.85 LHV Quantum PR Box= 1 Sunday, 1 August 2010 GHZ correlation (uniquely) satisfies: X ⊗X ⊗X|ψ￿ = |ψ￿ X ⊗ Y ⊗ Y |ψ￿ = |ψ￿ Y ⊗X ⊗ Y |ψ￿ = |ψ￿ |ψ￿ = |001￿+ |110￿ which also imply: Y ⊗ Y ⊗X|ψ￿ = −|ψ￿  Correlations in outcomes of local measurements} N. D. Mermin (1990), building on Greenberger, et al. (1989) Sunday, 1 August 2010 GHZ correlation (uniquely) satisfies: X ⊗X ⊗X|ψ￿ = |ψ￿ X ⊗ Y ⊗ Y |ψ￿ = |ψ￿ Y ⊗X ⊗ Y |ψ￿ = |ψ￿ |ψ￿ = |001￿+ |110￿ which also imply: Y ⊗ Y ⊗X|ψ￿ = −|ψ￿  Correlations in outcomes of local measurements} N. D. Mermin (1990), building on Greenberger, et al. (1989) Sunday, 1 August 2010 GHZ correlation (uniquely) satisfies: X ⊗X ⊗X|ψ￿ = |ψ￿ X ⊗ Y ⊗ Y |ψ￿ = |ψ￿ Y ⊗X ⊗ Y |ψ￿ = |ψ￿ |ψ￿ = |001￿+ |110￿ which also imply: Y ⊗ Y ⊗X|ψ￿ = −|ψ￿ GHZ “Paradox”: No (non-contextual) real number assignment of X and  Y can satisfy all of these.  Correlations in outcomes of local measurements} N. D. Mermin (1990), building on Greenberger, et al. (1989) Sunday, 1 August 2010 • A very clean way to express this correlation is to use the binary notation introduced above.  • I.e. the correlations “win” an XOR-game, nearly identical to the CHSH game. GHZ “paradox” s1 s2 m1 m2 m3 m1 ⊕m2 ⊕m3 = s1s2 J. Anders and D. E. Browne PRL (2009). s1 + s2 Sunday, 1 August 2010 Geometric approach to Bell inequalities Sunday, 1 August 2010 • Another useful representation of Bell inequalities is to form a vector from the conditional probabilities. • Each possible set of conditional probabilities is represented a point in a unit hypercube. ￿p =  p(0, 0) p(0, 1) p(1, 0) p(1, 1)  Geometric interpretation of BIs 0,0,0,0 1,1,1,1 p(s1, s2) ≡ p(m1 ⊕m2 = 1|s1, s2) conditional probability space Sunday, 1 August 2010 We can thus classify the regions of conditional probability space (2-D Schematic). Bell inequalities define facets of polytope. Quantum region LHV region: “Bell polytope” PR Box Marcel Froissart:  Nouvo Cimento (1981), B.S. Tsirelson, J. Sov. Math. (1987) Geometric interpretation of BIs Sunday, 1 August 2010 Convex polytopes • The convex hull of a set of vectors (vertices) in R^d. • Generalisation of polygons, polyhedra to higher d. • May be defined in terms of its vertices or its facets (as a set of inequalities defining half planes.) Facet Vertex Facet inequality Sunday, 1 August 2010 Geometric interpretation of BIs • The “Bell polytope” represents the region of conditional probabilities allowed in LHV theories. • It is a hyper-octahedron. The facets represent the CHSH inequalities (and normalisation conditions). Marcel Froissart:  Nouvo Cimento (1981). Sunday, 1 August 2010 Many-party Bell inequalities Sunday, 1 August 2010 Many-party Bell-inequalities • Werner and Wolf (2001) generalised the CHSH setting to n-parties. • We still keep 2-settings, 2-outputs per meas and consider conditional probs for the XOR of all outputs. s1 s2 m1 m2 sn mn · · ·M =￿ j mj Sunday, 1 August 2010 Many-party Bell-inequalities • Werner and Wolf (2001) generalised the CHSH setting to n-parties. • We still keep 2-settings, 2-outputs per meas and consider conditional probs for the XOR of all outputs. s1 s2 m1 m2 sn mn · · ·M =￿ j mj Sunday, 1 August 2010 Many-party Bell-inequalities • Werner and Wolf (2001) generalised the CHSH setting to n-parties. • We still keep 2-settings, 2-outputs per meas and consider conditional probs for the XOR of all outputs. • W & W derived the full n-party Bell polytope - and found that, for any n, it is a hyper-octahedron in 2^n dimensions. s1 s2 m1 m2 sn mn · · ·M =￿ j mj Sunday, 1 August 2010 Loopholes in Bell inequality Experiments Sunday, 1 August 2010 Loopholes in Bell Inequality experiments Sunday, 1 August 2010 Loopholes in Bell Inequality experiments • The beauty of Bell inequalities is that they are experimentally testable. Sunday, 1 August 2010 Loopholes in Bell Inequality experiments • The beauty of Bell inequalities is that they are experimentally testable. • However, Bell’s assumptions are strict. • Space-like separated measurements • Perfect detection efficiency • Measurement settings chosen at random (free-will). Sunday, 1 August 2010 Loopholes in Bell Inequality experiments • The beauty of Bell inequalities is that they are experimentally testable. • However, Bell’s assumptions are strict. • Space-like separated measurements • Perfect detection efficiency • Measurement settings chosen at random (free-will). • If these do not hold, then the BIs may not hold -  there may be loopholes. Sunday, 1 August 2010 Loopholes in Bell Inequality experiments Allowed LHV correlations under Bell’s assumptions Loopholes make the LHV region larger. Sunday, 1 August 2010 Loopholes in Bell Inequality experiments Allowed LHV correlations under Bell’s assumptions Loopholes make the LHV region larger. Allowed LHV correlations under actual experimental conditions Sunday, 1 August 2010 Bell inequalities vs Measurement-Based Quantum Computation Sunday, 1 August 2010 MBQC vs BIs vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 MBQC vs BIs • Both • Require (only) XOR side-processing to perform computational game or task. • This task is impossible (non-linear) with XOR gates alone (linear gates). vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 MBQC vs BIs vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 MBQC vs BIs • But • MBQC requires adaptive measurements, and thus measurements cannot be space-like separated. • Spatial separation is one of the most important assumptions in deriving the Bell inequalities. vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 This talk • Main result: • We will derive an equivalent of the Bell polytope for MBQC. • I.e. Within LHV theories, which measurement-based computations can be achieved? • Main tool: • Polytopes over Boolean functions. vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Boolean Functions Sunday, 1 August 2010 Boolean functions • A Boolean function is a map from n-bits to a single bit. • Every such function can be represented by a 2n bit vector listing the outputs for each of the 2n inputs. • E.g. • It is convenient to enumerate the Boolean functions as            where j =1, ..., 2^(2^n). ￿f =  f(0 . . . 00) f(0 . . . 01) f(0 . . . 10) ... f(1 . . . 11)  Sunday, 1 August 2010 Boolean functions • A Boolean function is a map from n-bits to a single bit. • Every such function can be represented by a 2n bit vector listing the outputs for each of the 2n inputs. • E.g. • It is convenient to enumerate the Boolean functions as            where j =1, ..., 2^(2^n). ￿f =  f(0 . . . 00) f(0 . . . 01) f(0 . . . 10) ... f(1 . . . 11)  • I.e. There 2^(2^n)  Boolean functions. Sunday, 1 August 2010 Boolean functions • A Boolean function is a map from n-bits to a single bit. • Every such function can be represented by a 2n bit vector listing the outputs for each of the 2n inputs. • E.g. • It is convenient to enumerate the Boolean functions as            where j =1, ..., 2^(2^n). ￿f =  f(0 . . . 00) f(0 . . . 01) f(0 . . . 10) ... f(1 . . . 11)  • I.e. There 2^(2^n)  Boolean functions. fj(￿s) Sunday, 1 August 2010 Boolean functions • Every Boolean function may be expressed as a polynomial (modulo 2) (known as “algebraic normal form”). • E.g. if input is the bitstring          ￿s = s1s2 . . . sn f(s) = a0 + a1s1 + a2s2 + · · · + a12s1s2 + · · · Sunday, 1 August 2010 Boolean functions • Every Boolean function may be expressed as a polynomial (modulo 2) (known as “algebraic normal form”). • E.g. if input is the bitstring          ￿s = s1s2 . . . sn f(s) = a0 + a1s1 + a2s2 + · · · + a12s1s2 + · · · Sunday, 1 August 2010 Boolean functions • Every Boolean function may be expressed as a polynomial (modulo 2) (known as “algebraic normal form”). • E.g. if input is the bitstring • In other words, any Boolean function can be expressed as a sequence of XOR (add mod 2) and AND (multiply) gates. ￿s = s1s2 . . . sn f(s) = a0 + a1s1 + a2s2 + · · · + a12s1s2 + · · · Sunday, 1 August 2010 Boolean functions • Every Boolean function may be expressed as a polynomial (modulo 2) (known as “algebraic normal form”). • E.g. if input is the bitstring • In other words, any Boolean function can be expressed as a sequence of XOR (add mod 2) and AND (multiply) gates. • The degree of the polynomial is a useful way of classifying Boolean functions. ￿s = s1s2 . . . sn f(s) = a0 + a1s1 + a2s2 + · · · + a12s1s2 + · · · Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written ak ∈ {0, 1}l(s) = a0 + n￿ j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written ak ∈ {0, 1}l(s) = a0 + n￿ j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written • There are thus 2^(n+1) such functions, which we shall enumerate          where k =1, ..., 2^(n+1). ak ∈ {0, 1} lk(￿s) l(s) = a0 + n￿ j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written • There are thus 2^(n+1) such functions, which we shall enumerate          where k =1, ..., 2^(n+1). • All linear functions may be generated via XOR gates alone. ak ∈ {0, 1} lk(￿s) l(s) = a0 + n￿ j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written • There are thus 2^(n+1) such functions, which we shall enumerate          where k =1, ..., 2^(n+1). • All linear functions may be generated via XOR gates alone. • Linear functions are closed under composition. ak ∈ {0, 1} lk(￿s) l(s) = a0 + n￿ j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written • There are thus 2^(n+1) such functions, which we shall enumerate          where k =1, ..., 2^(n+1). • All linear functions may be generated via XOR gates alone. • Linear functions are closed under composition. • In contrast, by composing a quadratic gate (e.g. NAND) one can generate all Booleans. ak ∈ {0, 1} lk(￿s) l(s) = a0 + n￿ j=1 ajsj Sunday, 1 August 2010 Stochastic Boolean maps • Consider a stochastic machine which, given input string s, outputs          with probability    .  fj(￿s) λj ￿s j fj(￿s) choice: prob: λj Sunday, 1 August 2010 Stochastic Boolean maps • Consider a stochastic machine which, given input string s, outputs          with probability    .  • The probability that the output bit of the machine is 1, conditional upon the input s, is given by: fj(￿s) λj p(1|￿s) = ￿ j λjp(fj(￿s) = 1) ￿ j λj = 1 ￿s j fj(￿s) choice: prob: λj Sunday, 1 August 2010 Stochastic Boolean maps Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity:  p(fj(￿s) = 1) = fj(￿s) Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity:  • and thus obtain  p(fj(￿s) = 1) = fj(￿s) p(1|￿s) = ￿ j λjfj(￿s) Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity:  • and thus obtain  • or equivalently p(fj(￿s) = 1) = fj(￿s) p(1|￿s) = ￿ j λjfj(￿s) ￿p = ￿ j λj ￿fj Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity:  • and thus obtain  • or equivalently • This is a convex combination of real-space vectors and thus a polytope, we call it the Boolean polytope. p(fj(￿s) = 1) = fj(￿s) p(1|￿s) = ￿ j λjfj(￿s) ￿p = ￿ j λj ￿fj Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity:  • and thus obtain  • or equivalently • This is a convex combination of real-space vectors and thus a polytope, we call it the Boolean polytope. • Geometrically, it is a unit 2^n d. hypercube. p(fj(￿s) = 1) = fj(￿s) p(1|￿s) = ￿ j λjfj(￿s) ￿p = ￿ j λj ￿fj Sunday, 1 August 2010 The Linear Polytope lj(￿s)￿s jchoice: prob: λj Sunday, 1 August 2010 The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: lj(￿s)￿s jchoice: prob: λj Sunday, 1 August 2010 The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: • The output probability of a linear stochastic machine lies in the 2^(n+1) vertex polytope: lj(￿s) ￿p = 2n+1￿ j=1 λj￿lj ￿s jchoice: prob: λj Sunday, 1 August 2010 The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: • The output probability of a linear stochastic machine lies in the 2^(n+1) vertex polytope: • We shall call this the (n-bit) linear polytope. lj(￿s) ￿p = 2n+1￿ j=1 λj￿lj ￿s jchoice: prob: λj Sunday, 1 August 2010 The linear polytope •We can classify the linear polytope using standard techniques. • It has 2^(n+1) vertices in a 2^n dimensional space. • Can show that it is a hyper-octahedron. Sunday, 1 August 2010 Bell inequalities for MBQC Sunday, 1 August 2010 Bell inequalities for MBQC • Let us ask a “Bell inequality” type question for MBQC: • Using the correlations from a LHV theory, within an MBQC setting what computations can we achieve? vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC • If we allow side computation to be universal, we could access the full Boolean polytope with side computation alone. vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC • If we allow side computation to be universal, we could access the full Boolean polytope with side computation alone. • For our question to make sense we make the following key assumption: vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC • If we allow side computation to be universal, we could access the full Boolean polytope with side computation alone. • For our question to make sense we make the following key assumption: • Side-computation will be solely linear. vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC • To simplify further, let’s initially adopt the precise CHSH (Werner-Wolf) setup. • Spatially separated parties with independent inputs. • Output of computation encoded in the XOR of all outcome bits. s1 s2 m1 m2 sn mn · · · M = ￿ j mj Sunday, 1 August 2010 Bell inequalities for MBQC • What computations            can this setup perform? • LHV model may be stochastic and thus the computations may include stochastic maps - allowed computations will form a region of the Boolean polytope. M(￿s) LHV? Sunday, 1 August 2010 Bell inequalities for MBQC • What computations            can this setup perform? • LHV model may be stochastic and thus the computations may include stochastic maps - allowed computations will form a region of the Boolean polytope. M(￿s) LHV? Sunday, 1 August 2010 Bell inequalities for MBQC • What computations            can this setup perform? • LHV model may be stochastic and thus the computations may include stochastic maps - allowed computations will form a region of the Boolean polytope. • Randomness arises in LHV theories by random assignment of the hidden variables. M(￿s) LHV? Sunday, 1 August 2010 Bell inequalities for MBQC • What computations            can this setup perform? • LHV model may be stochastic and thus the computations may include stochastic maps - allowed computations will form a region of the Boolean polytope. • Randomness arises in LHV theories by random assignment of the hidden variables. • Hence, this region will be a convex polytope, whose vertices correspond to the deterministic computations. M(￿s) LHV? Sunday, 1 August 2010 Bell inequalities for MBQC • First let us consider a single box. • The most general deterministic relationships between output and input can be written: • I.e. there are only 4 1-bit to 1-bit functions. sj mj aj ∈ {0, 1} bj ∈ {0, 1}mj = aj + bjmj Sunday, 1 August 2010 Bell inequalities for MBQC • If we associates bit aj and bj with each box, the most general expression for the output XOR bit          is s1 s2 m1 m2 sn mn · · · M = ￿ j mj = ￿ j aj + ￿ j bjsj M = a+ ￿ j bjsj M(￿s) Sunday, 1 August 2010 Bell inequalities for MBQC M(￿s) = a+ ￿ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see M(￿s) = a+ ￿ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see • this is linear in s, M(￿s) = a+ ￿ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see • this is linear in s, • by suitable choice of aj and bj all 2^(n+1) linear functions can be achieved. M(￿s) = a+ ￿ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see • this is linear in s, • by suitable choice of aj and bj all 2^(n+1) linear functions can be achieved. • Hence the full range of computations achievable by LHV correlations with XOR on the outcomes M(￿s) = a+ ￿ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see • this is linear in s, • by suitable choice of aj and bj all 2^(n+1) linear functions can be achieved. • Hence the full range of computations achievable by LHV correlations with XOR on the outcomes • is the Linear Polytope. M(￿s) = a+ ￿ j bjsj Sunday, 1 August 2010 The linear polytope vs the Werner Wolf polytope Sunday, 1 August 2010 The linear polytope vs the Werner Wolf polytope • The linear polytope is a hyper-octahedron with 2^(n+1) vertices. • The Werner-Wolf polytope is a hyper-octahedron with 2^(n+1) vertices. • Are they the same polytope? Sunday, 1 August 2010 The linear polytope vs the Werner Wolf polytope • The linear polytope is a hyper-octahedron with 2^(n+1) vertices. • The Werner-Wolf polytope is a hyper-octahedron with 2^(n+1) vertices. • Are they the same polytope? • Yes! In fact, the derivation above is essentially a line-by-line recasting of Werner and Wolf (2001). Sunday, 1 August 2010 The linear polytope vs the Werner Wolf polytope • The linear polytope is a hyper-octahedron with 2^(n+1) vertices. • The Werner-Wolf polytope is a hyper-octahedron with 2^(n+1) vertices. • Are they the same polytope? • Yes! In fact, the derivation above is essentially a line-by-line recasting of Werner and Wolf (2001). • Our derivation is a computational reformulation of the traditional Bell inequalities. Sunday, 1 August 2010 Bell inequalities for MBQC • So is this a failure? Sunday, 1 August 2010 Bell inequalities for MBQC • So is this a failure? • We have reproduced a 10-year old result. Sunday, 1 August 2010 Bell inequalities for MBQC • So is this a failure? • We have reproduced a 10-year old result. • We have failed to derive Bell inequalities relevant to standard MBQC since that utilises adaptive measurements. Sunday, 1 August 2010 Bell inequalities for MBQC • So is this a failure? • We have reproduced a 10-year old result. • We have failed to derive Bell inequalities relevant to standard MBQC since that utilises adaptive measurements. • However, sometimes new representations give new insights.... Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. • Since the LHV region is the linear polytope, and since linear functions are closed under composition. Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. • Since the LHV region is the linear polytope, and since linear functions are closed under composition. • Introducing extra linear computation will never introduce a loophole! Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. • Since the LHV region is the linear polytope, and since linear functions are closed under composition. • Introducing extra linear computation will never introduce a loophole! • All known loopholes must be associated with some non-linear computation. Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. • Since the LHV region is the linear polytope, and since linear functions are closed under composition. • Introducing extra linear computation will never introduce a loophole! • All known loopholes must be associated with some non-linear computation. • This allows us to weaken our assumptions and derive the same Bell inequalities. Sunday, 1 August 2010 An example: pre-processing in GHZ • Notice the third input depends upon the other two! s1 s2 m1 m2 m3 m1 ⊕m2 ⊕m3 = s1s2 s1 + s2 Sunday, 1 August 2010 An example: pre-processing in GHZ • Notice the third input depends upon the other two! • Why does this not induce a loophole? s1 s2 m1 m2 m3 m1 ⊕m2 ⊕m3 = s1s2 s1 + s2 Sunday, 1 August 2010 An example: pre-processing in GHZ • Notice the third input depends upon the other two! • Why does this not induce a loophole? • In an experiment, we simulate the dependency using post-selection. s1 s2 m1 m2 m3 m1 ⊕m2 ⊕m3 = s1s2 s1 + s2 Sunday, 1 August 2010 An example: GHZ • In an experimental test of GHZ, the third input is set at random. •We then post-select our data, and only keep data where                 . s1 s2 m1 m2 m3 r r = s1 + s2 Sunday, 1 August 2010 An example: GHZ • In an experimental test of GHZ, the third input is set at random. •We then post-select our data, and only keep data where                 . • Does this induce a detection loop-hole? No, it doesn’t... s1 s2 m1 m2 m3 r r = s1 + s2 Sunday, 1 August 2010 Linear measurement post-selection • Consider a more general setting. Let us set all inputs to n measurements as n uniformly random bits. • Let s be the input bit-string (provided by a referee, say). • We can post-select data such that each rj is a linear function of the bits in s. m1 m2 mn · · · r1 r2 rn M = a+ ￿ j bjrj Sunday, 1 August 2010 Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. Sunday, 1 August 2010 Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. M = a+ ￿ j bjrj Sunday, 1 August 2010 Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. • M is linear in rj. The rj’s are linear in s. Hence M is linear in s. M = a+ ￿ j bjrj Sunday, 1 August 2010 Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. • M is linear in rj. The rj’s are linear in s. Hence M is linear in s. • M remains inside the linear polytope and no loopholes are induced - the LHV region is no larger than before. M = a+ ￿ j bjrj Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. m1 m2 r1 r2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. m1 m2 r1 r2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. m1 m2 s1 m1 + s2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. • Since mj  are linear in r, M will remain within the linear polytope! m1 m2 s1 m1 + s2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. • Since mj  are linear in r, M will remain within the linear polytope! • This allows us to simulate linearly adaptive measurements, m1 m2 s1 m1 + s2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. • Since mj  are linear in r, M will remain within the linear polytope! • This allows us to simulate linearly adaptive measurements, • And the linear polytope will still describe all LHV correlations. m1 m2 s1 m1 + s2 Sunday, 1 August 2010 Computational Bell inequalities Sunday, 1 August 2010 Computational Bell Inequalities • We can use these observations to generalise the traditional Bell inequalities. Sunday, 1 August 2010 Computational Bell Inequalities • We can use these observations to generalise the traditional Bell inequalities. • A computational Bell inequality is a facet of the polytope of Boolean stochastic maps achieved in any LHV theory • On a random m-bit input string s • Given n 2-setting, 2-outcome space-like separated measurements • With post-selection of measurement settings which are a linear function of input data and other measurement outcomes (simulated linear adaptivity) • And arbitrary linear pre- and post-computation. Sunday, 1 August 2010 Computational Bell Inequalities • The “Computational Bell inequalities” are easy to characterise. • For n ≥ m they are facets of the m-bit linear polytope. • Setting n = m and forbidding post-selection, we recover the traditional definition of CHSH inequalities. Sunday, 1 August 2010 • A significant strand of Bell inequality research has been to characterise the set of conditional probabilities / stochastic maps allowed within Quantum Mechanics. From LHV to Quantum Correlations [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 • A significant strand of Bell inequality research has been to characterise the set of conditional probabilities / stochastic maps allowed within Quantum Mechanics. • Usually only non- adaptive measurements are considered. From LHV to Quantum Correlations [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 • A significant strand of Bell inequality research has been to characterise the set of conditional probabilities / stochastic maps allowed within Quantum Mechanics. • Usually only non- adaptive measurements are considered. • But in our new framework, we can also allow extra parties, and simulated linear adaptive measurement. From LHV to Quantum Correlations [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 • A significant strand of Bell inequality research has been to characterise the set of conditional probabilities / stochastic maps allowed within Quantum Mechanics. • Usually only non- adaptive measurements are considered. • But in our new framework, we can also allow extra parties, and simulated linear adaptive measurement. • Do these enlarge the quantum region? From LHV to Quantum Correlations [1] Known as Tsirelson - Landau - Masanes region. A bigger quantum set? Sunday, 1 August 2010 • Yes! • For a fixed n, • Allowing extra parties • Allowing linear post-selection (simulated adaptivity). • can increase the quantum region. From LHV to Quantum Correlations Sunday, 1 August 2010 • Yes! • For a fixed n, • Allowing extra parties • Allowing linear post-selection (simulated adaptivity). • can increase the quantum region. • This can provide a greater degree of violation of Bell Inequalities than in the standard setting. From LHV to Quantum Correlations Sunday, 1 August 2010 Quantum correlations with adaptive measurements • For example, if we limit the number of parties to 6. • With linear adaptive measurement we can access the deterministic 3-bit AND function. • The triple product s1s2s3 of input bits s1, s2, s3. • With no adaptivity, deterministic computation of this function is impossible with only 6 measurements [1]. [1] In Hoban et al (2010 - arxiv next week) we show that 2^(n-1) qubits are required to acheive an n-bit AND deterministically with no adaptivity. linearlinear linear Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. • This allowed us to characterise all 2-setting, 2-output Bell inequalities in terms of the linear Boolean polytope. Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. • This allowed us to characterise all 2-setting, 2-output Bell inequalities in terms of the linear Boolean polytope. • And made it clear that extra linear computations (including simulated adaptivity) do not lead to loopholes. Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. • This allowed us to characterise all 2-setting, 2-output Bell inequalities in terms of the linear Boolean polytope. • And made it clear that extra linear computations (including simulated adaptivity) do not lead to loopholes. • This enables one to consider a richer structure of quantum correlations in the context of BIs (including the adaptive measurements arising in MBQC) which we are only starting to investigate. Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. • This allowed us to characterise all 2-setting, 2-output Bell inequalities in terms of the linear Boolean polytope. • And made it clear that extra linear computations (including simulated adaptivity) do not lead to loopholes. • This enables one to consider a richer structure of quantum correlations in the context of BIs (including the adaptive measurements arising in MBQC) which we are only starting to investigate. • Are Bell inequality violations more about non-linearity than non-locality...? Sunday, 1 August 2010 Acknowledgements • Joint work with members of my UCL group • Matty Hoban, Janet Anders, Earl Campbell and Klearchos Loukopoulos. • These ideas benefitted from discussions with Robert Raussendorf, Robert Spekkens, Miguel Navascues,  Akimasa Miyake, Robin Blume-Kohout Debbie Leung and many others... • References • R. Werner and M. Wolf, Phys. Rev. A 64 32112 (2001) • J. Anders and D. E. Browne, Phys. Rev. Lett.  (2009) • M. J. Hoban, E.T. Campbell, K. Loukopoulos, D.E. Browne, "Non-adaptive measurement-based quantum computation and multi-party Bell inequalities", arxiv very very soon. • M. J. Hoban and D. E. Browne, Bell inequalities and adaptive measurements, arxiv soon. Sunday, 1 August 2010

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
United States 10 0
China 5 17
Japan 2 0
Canada 1 0
City Views Downloads
Beijing 5 0
Arlington 4 0
Unknown 3 3
Tokyo 2 0
Ashburn 2 0
Vancouver 1 0
Sunnyvale 1 0

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

Share

Share to:

Comment

Related Items