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

Correlations in Measurement-Based Quantum Computing and Bell Inequalities Browne, Daniel 2010

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

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
[if-you-see-this-DO-NOT-CLICK]
Vancouver Invited Browne.pdf [ 1.21MB ]
[if-you-see-this-DO-NOT-CLICK]
[if-you-see-this-DO-NOT-CLICK]
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
Original Record: 1.0103168 +original-record.json
Full Text
1.0103168.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 2010Quantum Foundations (Measurement- Based) Quantum Computation Sunday, 1 August 2010Measurement-based quantum computation Sunday, 1 August 2010Measurement-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 2010Measurement-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 2010Measurement-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 2010Measurement-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 2010Measurement-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 2010Measurement-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 2010Measurement-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). s j ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010Measurement-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). s j ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010Measurement-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 s j ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010Measurement-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 s j ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010Measurement-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 s j ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010Measurement-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 2010Bell inequalities Sunday, 1 August 2010Bell inequalities Sunday, 1 August 2010Bell inequalities • Bell inequalities (BIs) express restrictions on the joint probability distributions for spatially separated measurements in local hidden variable (LHV) theories. Sunday, 1 August 2010CHSH 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 ,s 2 = p(m1 ⊕m2 = 0| s1, s2)− p(m1 ⊕m2 = 1| s1, s2) Sunday, 1 August 2010CHSH 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 ,s 2 = p(m1 ⊕m2 = 0| s1, s2)− p(m1 ⊕m2 = 1| s1, s2) E0 , 0 + E0 , 1 + E1 , 0 − E1 , 1 ≤ 2 Sunday, 1 August 2010CHSH 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 2010CHSH 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 2010CHSH 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) E 0,0 + E 0,1 + E 1,0 − E 1,1 = 4 Sunday, 1 August 2010CHSH 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 ,s 2 = p(m1 ⊕m2 = 0| s1, s2)− p(m1 ⊕m2 = 1| s1, s2) Sunday, 1 August 2010CHSH 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 ,s 2 p(m1 ⊕m2 = s1s2 | s1s2 ) ≤ 3 4 [1] QIP Folklore: earliest reference I know: Wim Van Dam, PHD Thesis (2000) Es1 ,s 2 = p(m1 ⊕m2 = 0| s1, s2)− p(m1 ⊕m2 = 1| s1, s2) Sunday, 1 August 2010CHSH 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 ,s 2 p(m1 ⊕m2 = s1s2 | s1s2 ) ≤ 3 4 [1] QIP Folklore: earliest reference I know: Wim Van Dam, PHD Thesis (2000) Es1 ,s 2 = p(m1 ⊕m2 = 0| s1, s2)− p(m1 ⊕m2 = 1| s1, s2) Sunday, 1 August 2010CHSH 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 ⊕m 2 = s 1 s 2 m 1 XOR m 2 = s1 AND s2 Sunday, 1 August 2010CHSH game 1 4 ￿ s1 ,s 2 p (m 1 + m 2 = s 1 s 2 ) ≤ 3 4 ≤ 2 + √ 2 4 ≈ 0.85 LHV Quantum PR Box= 1 Sunday, 1 August 2010CHSH game • CHSH inequalities bound the mean success probability of the game. 1 4 ￿ s1 ,s 2 p (m 1 + m 2 = s 1 s 2 ) ≤ 3 4 ≤ 2 + √ 2 4 ≈ 0.85 LHV Quantum PR Box= 1 Sunday, 1 August 2010CHSH 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 ,s 2 p (m 1 + m 2 = s 1 s 2 ) ≤ 3 4 ≤ 2 + √ 2 4 ≈ 0.85 LHV Quantum PR Box= 1 Sunday, 1 August 2010GHZ 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 2010GHZ 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 2010GHZ 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” s 1 s 2 m 1 m 2 m 3 m1 ⊕m2 ⊕m3 = s1s2 J. Anders and D. E. Browne PRL (2009). s 1 + s 2 Sunday, 1 August 2010Geometric 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 2010We 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 2010Convex 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 2010Geometric 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 2010Many-party Bell inequalities Sunday, 1 August 2010Many-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. s 1 s 2 m 1 m 2 s n m n · · ·M =￿ j mj Sunday, 1 August 2010Many-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. s 1 s 2 m 1 m 2 s n m n · · ·M =￿ j mj Sunday, 1 August 2010Many-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. s 1 s 2 m 1 m 2 s n m n · · ·M =￿ j mj Sunday, 1 August 2010Loopholes in Bell inequality Experiments Sunday, 1 August 2010Loopholes in Bell Inequality experiments Sunday, 1 August 2010Loopholes in Bell Inequality experiments • The beauty of Bell inequalities is that they are experimentally testable. Sunday, 1 August 2010Loopholes 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 2010Loopholes 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 2010Loopholes in Bell Inequality experiments Allowed LHV correlations under Bell’s assumptions Loopholes make the LHV region larger. Sunday, 1 August 2010Loopholes 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 2010Bell inequalities vs Measurement-Based Quantum Computation Sunday, 1 August 2010MBQC vs BIs vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010MBQC 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 2010MBQC vs BIs vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010MBQC 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 2010This 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 2010Boolean Functions Sunday, 1 August 2010Boolean 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 2010Boolean 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 2010Boolean 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. f j ( ￿s) Sunday, 1 August 2010Boolean 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 = s 1 s 2 . . . s n f (s) = a 0 + a 1s1 + a 2s2 + · · · + a 12s1s2 + · · · Sunday, 1 August 2010Boolean 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 = s 1 s 2 . . . s n f (s) = a 0 + a 1s1 + a 2s2 + · · · + a 12s1s2 + · · · Sunday, 1 August 2010Boolean 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 = s 1 s 2 . . . s n f (s) = a 0 + a 1s1 + a 2s2 + · · · + a 12s1s2 + · · · Sunday, 1 August 2010Boolean 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 = s 1 s 2 . . . s n f (s) = a 0 + a 1s1 + a 2s2 + · · · + a 12s1s2 + · · · Sunday, 1 August 2010Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written a k ∈ {0, 1}l ( s ) = a 0 + n￿ j=1 a j s j Sunday, 1 August 2010Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written a k ∈ {0, 1}l ( s ) = a 0 + n￿ j=1 a j s j Sunday, 1 August 2010Linear 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). a k ∈ {0, 1} l k ( ￿s ) l ( s ) = a 0 + n￿ j=1 a j s j Sunday, 1 August 2010Linear 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. a k ∈ {0, 1} l k ( ￿s ) l ( s ) = a 0 + n￿ j=1 a j s j Sunday, 1 August 2010Linear 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. a k ∈ {0, 1} l k ( ￿s ) l ( s ) = a 0 + n￿ j=1 a j s j Sunday, 1 August 2010Linear 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. a k ∈ {0, 1} l k ( ￿s ) l ( s ) = a 0 + n￿ j=1 a j s j Sunday, 1 August 2010Stochastic Boolean maps • Consider a stochastic machine which, given input string s, outputs          with probability    .  f j ( ￿s) λj ￿s j fj ( ￿s ) choice: prob: λj Sunday, 1 August 2010Stochastic 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:  f j ( ￿s) λj p(1 | ￿s) = ￿ j λjp(fj(￿s) = 1) ￿ j λ j = 1 ￿s j fj ( ￿s ) choice: prob: λj Sunday, 1 August 2010Stochastic Boolean maps Sunday, 1 August 2010Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity:  p(fj(￿s) = 1) = fj(￿s) Sunday, 1 August 2010Stochastic 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 2010Stochastic 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 2010Stochastic 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 2010Stochastic 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 2010The Linear Polytope l j ( ￿s)￿s jchoice: prob: λj Sunday, 1 August 2010The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: l j ( ￿s)￿s jchoice: prob: λj Sunday, 1 August 2010The 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: l j ( ￿s) ￿p = 2n+1￿ j=1 λj￿lj ￿s jchoice: prob: λj Sunday, 1 August 2010The 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. l j ( ￿s) ￿p = 2n+1￿ j=1 λj￿lj ￿s jchoice: prob: λj Sunday, 1 August 2010The 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 2010Bell inequalities for MBQC Sunday, 1 August 2010Bell 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 2010Bell inequalities for MBQC vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010Bell 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 2010Bell 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 2010Bell 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 2010Bell 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. s 1 s 2 m 1 m 2 s n m n · · · M = ￿ j mj Sunday, 1 August 2010Bell 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 2010Bell 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 2010Bell 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 2010Bell 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 2010Bell 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. s j m j a j ∈ {0, 1} b j ∈ {0 , 1}m j = a j + b j m j Sunday, 1 August 2010Bell inequalities for MBQC • If we associates bit aj and bj with each box, the most general expression for the output XOR bit          is s 1 s 2 m 1 m 2 s n m n · · · M = ￿ j m j = ￿ j a j + ￿ j b jsj M = a + ￿ j b j sj M ( ￿s ) Sunday, 1 August 2010Bell inequalities for MBQC M ( ￿s) = a + ￿ j b jsj Sunday, 1 August 2010Bell inequalities for MBQC • We see M ( ￿s) = a + ￿ j b jsj Sunday, 1 August 2010Bell inequalities for MBQC • We see • this is linear in s, M ( ￿s) = a + ￿ j b jsj Sunday, 1 August 2010Bell 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 b jsj Sunday, 1 August 2010Bell 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 b jsj Sunday, 1 August 2010Bell 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 b jsj Sunday, 1 August 2010The linear polytope vs the Werner Wolf polytope Sunday, 1 August 2010The 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 2010The 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 2010The 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 2010Bell inequalities for MBQC • So is this a failure? Sunday, 1 August 2010Bell inequalities for MBQC • So is this a failure? • We have reproduced a 10-year old result. Sunday, 1 August 2010Bell 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 2010Bell 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 2010Loopholes and linearity • Our Bell polytope is the polytope of linear functions. Sunday, 1 August 2010Loopholes 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 2010Loopholes 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 2010Loopholes 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 2010Loopholes 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 2010Loopholes 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 2010An example: pre-processing in GHZ • Notice the third input depends upon the other two! s 1 s 2 m 1 m 2 m 3 m1 ⊕m2 ⊕m3 = s1s2 s 1 + s 2 Sunday, 1 August 2010An example: pre-processing in GHZ • Notice the third input depends upon the other two! • Why does this not induce a loophole? s 1 s 2 m 1 m 2 m 3 m1 ⊕m2 ⊕m3 = s1s2 s 1 + s 2 Sunday, 1 August 2010An 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. s 1 s 2 m 1 m 2 m 3 m1 ⊕m2 ⊕m3 = s1s2 s 1 + s 2 Sunday, 1 August 2010An 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                 . s 1 s 2 m 1 m 2 m 3 r r = s 1 + s 2 Sunday, 1 August 2010An 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... s 1 s 2 m 1 m 2 m 3 r r = s 1 + s 2 Sunday, 1 August 2010Linear 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. m 1 m 2 m n · · · r 1 r 2 r n M = a + ￿ j b j r j Sunday, 1 August 2010Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. Sunday, 1 August 2010Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. M = a + ￿ j b j r j Sunday, 1 August 2010Linear 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 b j r j Sunday, 1 August 2010Linear 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 b j r j Sunday, 1 August 2010Linear measurement post-selection • But we can go further. m 1 m 2 r 1 r 2 Sunday, 1 August 2010Linear 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. m 1 m 2 r 1 r 2 Sunday, 1 August 2010Linear 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. m 1 m 2 s 1 m1 + s 2 Sunday, 1 August 2010Linear 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! m 1 m 2 s 1 m1 + s 2 Sunday, 1 August 2010Linear 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, m 1 m 2 s 1 m1 + s 2 Sunday, 1 August 2010Linear 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. m 1 m 2 s 1 m1 + s 2 Sunday, 1 August 2010Computational Bell inequalities Sunday, 1 August 2010Computational Bell Inequalities • We can use these observations to generalise the traditional Bell inequalities. Sunday, 1 August 2010Computational 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 2010Computational 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 2010Quantum 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 2010Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. Sunday, 1 August 2010Summary • 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 2010Summary • 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 2010Summary • 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 2010Summary • 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 2010Acknowledgements • 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 15 0
China 7 17
Japan 4 0
Canada 2 0
Romania 2 0
United Kingdom 1 0
Czech Republic 1 0
Austria 1 0
Poland 1 0
Australia 1 1
City Views Downloads
Unknown 8 4
Ashburn 5 0
Beijing 5 0
Arlington 4 0
Tokyo 2 0
Hiroshima 2 0
Shenzhen 2 17
Ottawa 1 0
Sunnyvale 1 0
Saint Lucia 1 1
Seattle 1 0
Vancouver 1 0
Wilmington 1 0

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

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>
                        
                    
IIIF logo 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-0103168/manifest

Comment

Related Items