This is the homepage of Bilkent Quantum Information and Topology Group.
Postdoc positions available, visit Open Positions
Math 421 - Introduction to quantum computing
Previous reading seminars
Quantum contextuality (Kochen–Specker 67 and Bell 66) is first observed in the Bell–Kochen–Specker “no-go” theorem. Here the word “context” refers to a set $A_1,A_2,\cdots$ of pairwise commuting observables, i.e. Hermitian matrices. The no-go result demonstrates the impossibility of associating an outcome (eigenvalue) to each of the observables independent of the context. Simplest proofs are the Mermin square and star constructions (Mermin 93). These constructions can be seen as the first obstruction to the impossibility of reproducing the predictions of quantum theory by hidden variable models. In recent work, we showed that Kochen–Specker type contextuality has a topological characterization (Okay et al). This is initially achieved by introducing a (co)chain complex $C$ whose second cohomology group contains an obstruction class $\beta$ that detects contextuality. Another way of producing such no-go results is to rely on symmetry. The corresponding obstruction class $\Phi$ belongs to a bicomplex reminiscent of the first page of a spectral sequence associated to the action of the symmetry group on the chain complex $C$. A striking consequence of this approach is the relationship between the two obstruction classes, $\beta$ and $\Phi$, hence two different ways of constructing no-go results, that naturally follows from the homological formulation. Moreover, this framework is powerful enough to provide a topological basis for more general types of no-go results, in the form of violation of inequalities, that depend on a fixed quantum state $\rho$ (positive semidefinite matrix of trace $1$). For instance, the Clauser–Horne–Shimony–Holt (CHSH) inequality can be represented by the Mermin star construction, thus can be given a cohomological explanation.
Kochen–Specker type contextuality can be formulated in the form of a linear constraint system. This formulation is better suited to elevate the algebraic discussion of chain complexes to a topological one involving cell (CW) complexes. A linear constraint system (LCS) is specified by a linear equation $Mx=b$ defined over the ring $\mathbb{Z}/d$ of integers mod $d$ (Cleve–Mittal 14). An operator solution to the LCS is a set of unitary matrices (whose order divides $d$) that satisfy certain commutation relations and linear relations imposed by the equation $Mx=b$. Solutions in $U(1)$ are called scalar solutions. In this framework a proof of contextuality, in the sense of Kochen–Specker, is demonstrated by showing that no scalar solutions exist. More conveniently, a LCS can be described by a hypergraph $\mathfrak{H}=(V,E)$ with an incidence weight given by the matrix $M$ together with a function $b:E\to \mathbb{Z}/d$ on the edge set. Our topological approach in Okay–Raussendorf 20 associates to the hypergraph a $2$-dimensional cell complex $X_{\mathfrak{H}}$, called a topological realization, such that the function $b$ can be regarded as a $2$-cocycle, and thus gives a class in $H^2(X_{\mathfrak{H}},\mathbb{Z}/d)$. Then our main result says that if the topological realization is simply connected then the LCS cannot be contextual, i.e. it is non-contextual. This result generalizes an earlier graph-theoretic characterization of Arkhipov 12, that holds only for particular hypergraphs and for $d=2$, to arbitrary hypergraphs and any $d\geq 2$.
To be able to use the full power of homotopy theory we need to introduce classifying spaces of certain type. Let $G$ be a topological group, the main example will be the unitary group $U(m)$. The classifying space $BG$ is a topological space constructed using simplicial techniques. More precisely, it is assembled from the space of homomorphisms $\text{Hom}(F^n,G)$ (can be identified with $G^n$) where $F^n$ is the free group on $n$ elements. In fact, $\lbrace F^n \rbrace_{n\geq 0}$ can be given the structure of a cosimplicial group, which induces the simplicial structure on the spaces of homomorphisms. More generally, given an endofunctor $\tau$ on the category of groups one can construct (Adem–Cohen–Torres Giese 12) classifying spaces, denoted by $B(\tau,G)$, assembled from the spaces of homomorphisms $\text{Hom}(\tau(F^n),G)$. Main examples for $\tau$ are the abelianization functor, its mod $d$-reduction, and the $q$-th stage of the descending central series. The resulting spaces are denoted by $B(\mathbb{Z},G)$, $B(\mathbb{Z}/d,G)$, and $B(\Gamma_q,G)$; respectively. The word “classifying space” is justified by the observation that $B(\tau,G)$ classifies certain types of principal $G$-bundles, so-called bundles with $\tau$-structure (generalizing transitionally commutative bundles introduced in Adem–Gomez 15). Therefore understanding the homotopy type of $B(\tau,G)$ has its own motivation for algebraic topologists. However, the homotopy type of this space is largely unknown, except in some particular cases including low-dimensional Lie groups (Antolin et al), stable classical groups (Gritschacher–Hausmann 19), certain finite groups (Okay 18). For stable classical groups $B(\Gamma_q,G)$ gives rise to nilpotent versions of topological $K$-theory.
Turning back to the topological study of quantum contextuality we describe a refinement of the homotopical approach using classifying spaces. The main observation is the topological interpretation of operator solutions for LCSs over $\mathbb{Z}/d$. Let $\mu_d$ denote the subgroup of $U(1)$ consisting of elements whose order divides $d$. The classifying space for contextuality, denoted by $B_\cx(d,m)$, is a quotient space of $B(\mathbb{Z}/d,U(m))$ obtained by identifying, at the level of $n$-simplices, $(A_1,\cdots,A_n)\sim (A_1',\cdots,A_n')$ whenever $A_i = \alpha_i A_i'$ for some $\alpha_i\in \mu_d$. Given a LCS described by $(\mathfrak{H},b)$ consider an operator solution, more specifically, a function $T:V\to U(m)$ satisfying
$T(v)^d=I_m$ for each $v\in V$,
$T(v)T(v')=T(v')T(v)$ whenever $v,v'$ belong to the same edge $e\in E$,
a linear constraint specified by the equation $Mx=b$.
The key observation in Okay 20 is that $T$ can be used to construct a map of spaces
defined up to homotopy, for a given topological realization $X_{\mathfrak{H}}$. Then we can introduce an equivalence relation on the collection of operator solutions using the notion of homotopy: $T\sim T'$ whenever $f_T \simeq f_{T'}$. This gives rise to a homotopical classification of operator solutions. The equivalence classes are given by the set $[X,B_{\text{cx}}(d,m)]$ of (pointed) homotopy classes of maps. Since $X$ is $2$-dimensional, the computation of this set turns out to be completely algebraic. It boils down to understanding the $\pi_1$-module structure of $\pi_2$ where $\pi_i=\pi_i(B_{\text{cx}}(d,m))$. Currently, these low dimensional homotopy groups are unknown. The stabilization process that replaces the unitary group $U(m)$ with the stable unitary group $U$ gives a way to overcome this difficulty at the cost of obtaining a coarser classification. It turns out that $B(\mathbb{Z}/d,U)$ represents a generalized cohomology theory denoted by $k\mu_d$, called the $d$-torsion commutative $K$-theory. On the other hand, using methods from stable homotopy theory the quotient space $B_{\text{cx}}(d,m)$ can also be stabilized to give a new generalized cohomology theory, the $C(d,m)$-cohomology. The elements of $C(d,m)(X_\mathfrak{H})$ are “stable” classes of operator solutions for the associated LCS. There is a surprising connection to the classification (Kitaev 13) of symmetry-protected topological (SPT) phases via stable homotopy theory. This can be best demonstrated in the real case, i.e. using $O(m)$ instead of $U(m)$. The corresponding cohomology theory is denoted by $C_{\mathbb{R}}(2,m)$ ($d=2$ in the real case). This cohomology theory contains information both on quantum contextuality and SPT phases.
Next, we describe the resource-theoretic value of quantum contextuality and how the topological framework can facilitate this study. Contextuality has been established as a computational resource in two prominent schemes of quantum computation:
Measurement-based quantum computation (MBQC) (Robert 13)
Quantum computation with magic states (QCM) (Howard et al).
In the first scheme a computation is implemented by a sequence of measurements on an initial quantum state $\rho$ for $n$-qubits—a quantum system whose Hilbert space is $(\mathbb{C}^2)^{\otimes n}$. This scheme can compute a nonlinear Boolean function with a high success probability if contextuality is present. The basic example is obtained from a version of the Mermin star LCS and choosing the Greenberger–Horne–Zeilinger (GHZ) state as the initial state $\rho$. The computational power is a consequence of the non-classical correlations created by $\rho$. In the second scheme the computational power is again achieved by a quantum state, usually called a magic state, and the computation is implemented by a sequence of Pauli measurements (Clifford gates can be ignored). Each measurement is described by a projector associated to the common eigenspace of a context given by an abelian subgroup of the Pauli group $P_n$—a certain finite subgroup of $U(p^n)$ isomorphic to an extraspecial $p$-group. The cases $p=2$ and $p\gt 2$ behave differently. When $p\gt 2$ contextuality can be characterized using Wigner functions, a quasi-probability representation of quantum states. This representation can be used to construct an efficient classical simulation algorithm for the quantum computation if and only if $\rho$ is non-contextual. Therefore contextuality is both necessary and sufficient for computational speedup. But, when $p=2$ this nice relationship does not hold anymore. We recently introduced in Zurel–Okay–Raussendorf a classical simulation algorithm based on a new hidden variable model for qubits ($p=2$). In this model any quantum state can be described as a probability distribution on a finite state space consisting of the vertices of a polytope $\Lambda_n$. This hidden variable model does not allow for deterministic outcomes, therefore cannot be studied in the Kochen–Specker paradigm. In this case the operation-theoretic approach of Spekkens (Spekkens 05) provides a suitable framework.
S. Kochen and E. P. Specker. “The Problem of Hidden Variables in Quantum Mechanics”. In: Journal of Mathematics and Mechanics 17.1 (1967), pp. 59–87
J. S. Bell. “On the problem of hidden variables in quantum mechanics”. In: Reviews of Modern Physics 38.3 (1966), p. 447
N. D. Mermin. “Hidden variables and the two theorems of John Bell”. In: Reviews of Modern Physics 65.3 (1993), p. 803.
C. Okay et al. “Topological proofs of contextuality in quantum mechanics”. In: Quantum Information & Computation 17.13-14 (2017), pp. 1135–1166.
R. Cleve and R. Mittal. “Characterization of binary constraint system games”. In: International Colloquium on Automata, Languages, and Programming. Springer. 2014, pp. 320–331.
C. Okay and R. Raussendorf. “Homotopical approach to quantum contextuality”. In: Quantum 4 (2020), p. 217.
A. Arkhipov. “Extending and characterizing quantum magic games”. In: MSc thesis (2012).
A. Adem, F. R. Cohen, and E. Torres Giese. “Commuting elements, simplicial spaces and filtrations of classifying spaces”. In: Math. Proc. Cambridge Philos. Soc. 152.1 (2012), pp. 91–114.
A. Adem and J. M. Gomez. “A classifying space for commutativity in Lie groups”. In: Algebr. Geom. Topol. 15.1 (2015), pp. 493–535.
O. Antolin-Camarena, S. P. Gritschacher, and B. Villarreal. “Classifying spaces for commutativity of low-dimensional Lie groups”. In: Mathematical Proceedings of the Cambridge Philosophical Society. Cambridge 11 University Press. 2019, pp. 1–46.
S. Gritschacher and M. Hausmann. “Commuting matrices and Atiyah’s real K-theory”. In: Journal of Topology 12.3 (2019), pp. 832–853.
C. Okay. “Spherical posets from commuting elements”. In: J. Group Theory 21.4 (2018), pp. 593–628.
C. Okay. “Commutative d-Torsion K-Theory and Its Applications”. In: arXiv preprint arXiv:2006.07542 (2020).
A. Kitaev. “On the classification of short-range entangled states”. Talk at Simons Center. 2013.
R. Raussendorf. “Contextuality in measurement-based quantum computation”. In: Physical Review A 88.2 (2013), p. 022322.
M. Howard et al. “Contextuality supplies the magic for quantum computation”. In: Nature 510.7505 (2014), p. 351.
M. Zurel, C. Okay, and R. Raussendorf. “A hidden variable model for universal quantum computation with magic states on qubits”. In: arXiv preprint arXiv:2004.01992 (2020).
R. W. Spekkens. “Contextuality for preparations, transformations, and unsharp measurements”. In: Physical Review A 71.5 (2005), p. 052108.