We study measurement-based quantum computation (MQC) using as a quantum resource the planar code state on a two-dimensional square lattice (planar analog of the toric code). It is shown that MQC with the planar code state can be efficiently simulated on a classical computer if at each step of MQC the sets of measured and unmeasured qubits correspond to connected subsets of the lattice. The simulation scheme is built upon Barahona's algorithm for computing the partition function of the Ising model on a planar graph. Our results provide a simulation method for MQC centered around planarity of graphs.
We study measurement-based quantum computation (MQC) using as a quantum resource the planar code state on a two-dimensional square lattice (planar analog of the toric code). It is shown that MQC with the planar code state can be efficiently simulated on a classical computer if at each step of MQC the sets of measured and unmeasured qubits correspond to connected subsets of the lattice. The simulation scheme is built upon Barahona's algorithm for computing the partition function of the Ising model on a planar graph. Our results provide a simulation method for MQC centered around planarity of graphs.
In this thesis, we consider the task of simulating measurement-based quantum computation (MBQC) on surface code states: the generalization of Kitaev's toric code to graphs embedded on a surface of higher genus. We define a family of higher genus graphs and a simple ordering of single qubit measurements, and find that simulating MBQC on any of the associated surface code states is equivalent to evaluating the inner-product between a product state and a surface code state on another graph. We further find that such an inner-product can always be written as a sum of one or more 2D classical Ising model partition functions, with appropriate couplings. For certain higher genus square lattices, we develop a means to evaluate this partition function in a number of steps that scales polynomially in the number of qubits, but exponentially in the genus of the embedded graph. The method makes use of the transfer matrix formalism for the Ising partition function, and a subsequent mapping to fermion operators. We synthesize these results to relate the simulation of MBQC on certain surface code states to a system of fermions interacting with the encoded qubits of the surface code. We identify a family of states in the code space of the surface code on our higher genus graphs for which MBQC can be simulated efficiently in all parameters, including the genus of the embedded graph. Finally, we identify two connections between the complexity of this task and entanglement.
We describe and analyze algorithms for classically simulating measurement of an n-qubit quantum state in the standard basis, that is, sampling a bit string from the probability distribution determined by the Born rule. Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states; unlike previously known techniques they do not require computation of marginal probabilities. Two classes of quantum states are considered: output states of polynomial-size quantum circuits, and ground states of local Hamiltonians with an inverse polynomial spectral gap. We show that our algorithms can significantly accelerate quantum circuit simulations based on tensor network contraction or low-rank stabilizer decompositions. As another striking consequence we obtain the first efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph and any schedule of measurements.
Abstract The measurement-based quantum computing paradigm relies on entangling the qubits of a register into a graph state and on measuring subsets of such register in order to condition the unmeasured qubits. The computation therefore, instead of being carried on only by one-qubit and two-qubits logic gates, is largely based on entanglement and measurement processes. Compared to the gate model architecture, in MBQC the overhead in terms of computation resources to synthesize logical qubits is higher. While gate model relies on a register of logical qubits whose number is set at the beginning of the computation and remains constant during the computation, in the MBQC the input qubits outnumber the output ones, due to the destructive nature of measurement processes. Still, we analytically prove and experimentally confirm that MBQC can be efficiently emulated on a classical software, reaching equal loads with respect to the gate-based approach in terms of average runtime and storage of memory. The numerical results confirm that despite the potential computational overhead due to the high entanglement of the initial graph state, the MBQC paradigm carries similar computational complexity, both in terms of time and memory, with respect to the gate-based approach.
We give efficient quantum algorithms to estimate the partition function of (i) the six-vertex model on a two-dimensional (2D) square lattice, (ii) the Ising model with magnetic fields on a planar graph, (iii) the Potts model on a quasi-2D square lattice and (iv) the Z 2 lattice gauge theory on a 3D square lattice.Moreover, we prove that these problems are BQP-complete, that is, that estimating these partition functions is as hard as simulating arbitrary quantum computation.The results are proven for a complex parameter regime of the models.The proofs are based on a mapping relating partition functions to quantum circuits introduced by Van den Nest et al (2009 Phys.Rev. A 80 052334) and extended here.
We introduce schemes for quantum computing based on local measurements on entangled resource states. This work elaborates on the framework established in Gross and Eisert [Phys. Rev. Lett. 98, 220503 (2007); quant-ph/0609149]. Our method makes use of tools from many-body physics---matrix product states, finitely correlated states, or projected entangled pairs states---to show how measurements on entangled states can be viewed as processing quantum information. This work hence constitutes an instance where a quantum information problem---how to realize quantum computation---was approached using tools from many-body theory and not vice versa. We give a more detailed description of the setting and present a large number of examples. We find computational schemes, which differ from the original one-way computer, for example, in the way the randomness of measurement outcomes is handled. Also, schemes are presented where the logical qubits are no longer strictly localized on the resource state. Notably, we find a great flexibility in the properties of the universal resource states: They may, for example, exhibit nonvanishing long-range correlation functions or be locally arbitrarily close to a pure state. We discuss variants of Kitaev's toric code states as universal resources, and contrast this with situations where they can be efficiently classically simulated. This framework opens up a way of thinking of tailoring resource states to specific physical systems, such as cold atoms in optical lattices or linear optical systems.
One-way quantum computation was first invented using the cluster state. Since then graph states, the generalization of the cluster state, were investigated and understood when they would enable such a measurement-based approach for quantum computation. Are there any other family of states, i.e., states with different entanglement structures, that can also serve as the universal resource for quantum computation? Recent study shows that the Affleck-Kennedy-Lieb-Tasaki (AKLT) states also provide a useful source. Here, we show that the spin-2 state on the square lattice is a universal resource for measurement-based quantum computation. We employ a POVM on all sites that convert the local 5-level system to 2-level, and the post-POVM state is a graph state, whose graph is in general non-planar. We then follow with another round of measurement to recover the planarity of the graphs by thinning. The resultant typical graphs are shown to reside in the supercritical phase of percolation via Monte Carlo simulations and the associated graph states are universal, implying the AKLT state is also universal.