Measurement-based Quantum Computation as a Tangram Puzzle Ashlesha Patil1Yosef P. Jacobson2Don Towsley3and Saikat Guha1 1Wyant College of Optical Sciences University of Arizona Tucson AZ USA

2025-05-02 0 0 1MB 7 页 10玖币

侵权投诉

Measurement-based Quantum Computation as a Tangram Puzzle

Ashlesha Patil,1, ∗Yosef P. Jacobson,2Don Towsley,3and Saikat Guha1

1Wyant College of Optical Sciences, University of Arizona, Tucson AZ USA

2Department of Computer Science, University of Arizona, Tucson AZ USA

3College of Information and Computer Sciences, University of Massachusetts, Amherst MA USA

Measurement-Based Quantum Computing (MBQC), proposed in 2001 is a model of quantum

computing that achieves quantum computation by performing a series of adaptive single-qubit mea-

surements on an entangled cluster state. Our project is aimed at introducing MBQC to a wide

audience ranging from high school students to quantum computing researchers through a Tangram

puzzle with a modiﬁed set of rules, played on an applet. The rules can be understood without any

background in quantum computing. The player is provided a quantum circuit, shown using gates

from a universal gate set, which the player must map correctly to a playing board using polyomi-

nos. Polyominos, or ‘puzzle blocks’ are the building blocks of our game. They consist of square tiles

joined edge-to-edge to form diﬀerent colored shapes. Each tile represents a single-qubit measurement

basis, diﬀerentiated by its color. Polyominos rest on a square-grid playing board, which signiﬁes

a cluster state. We show that mapping a quantum circuit to MBQC is equivalent to arranging

a set of polyominos—each corresponding to a gate in the circuit—on the playing board—subject

to certain rules, which involve rotating and deforming polyominos. We state the rules in simple

terms with no reference to quantum computing. The player has to place polyominos on the playing

board conforming to the rules. Any correct solution creates a valid realization of the quantum

circuit in MBQC. A higher-scoring correct solution ﬁlls up less space on the board, resulting in a

lower-overhead embedding of the circuit in MBQC, an open and a challenging research problem.

I. INTRODUCTION

The circuit model of quantum computing is the most

widely studied method to implement a quantum com-

puter. In this model, a set of universal quantum gates

is used to implement a quantum algorithm. A set of

nqubits, prepared in a product state, undergo unitary

operations (or quntum gates). At the end of the cir-

cuit, each qubit is measured oﬀ, collapsing the entangled

state of nqubits, to one of the 2nstates in the super-

position, thereby revealing the answer to the computa-

tion. The algorithm is encoded in the sequence of gates.

Gates are draws from a (small) set of universal gates.

This quantum circuit representation resembles a classi-

cal (Boolean) circuit made up of universal gates (e.g., the

NAND gate) evolving the classical state of a collection of

nbits. As a result, the circuit model of quantum com-

puting is very easy to understand. There are multiple

online courses that teach high-school and undergradu-

ate students, working professionals the basics of quantum

computing using the circuit model. Measurement-Based

Quantum Computing (MBQC) is another model of quan-

tum computation that has recently started regaining at-

tention, because of its promise in photonic quantum com-

puting. However, it is not yet widely known even in the

quantum computing community. Our project is aimed

at introducing MBQC to a wide audience ranging from

high-school students to quantum computing researchers.

It sets out to create a fun, open-source applet, similar to

the game of Tangram, through which the player learns

to map quantum circuits to MBQC. This applet is being

∗ashlesha@.arizona.edu

developed as a Education and Workforce Development

(EWD) initiative of the NSF ERC Center for Quantum

Networks (CQN) and we plan to use it for our outreach

activities. Moreover, high-score solutions to our game

will provide insights in resource eﬃcient compilations of

quantum circuits into MBQC: an open research prob-

lem relevant for photonic quantum computing, and dis-

tributed quantum computing over a network.

II. BACKGROUND

Unlike the circuit model, where qubits are passed

through gates, in the one way model of MBQC pro-

posed in 2001, quantum computation is achieved solely

by performing a series of adaptive single qubit measure-

ments on a highly connected entangled state called clus-

ter state [1, 2]. Cluster states form a class of entangled

state that can be represented graphically with nodes con-

nected by edges (Fig. 1b) such that the nodes correspond

to qubits prepared in |+istate and every edge represents

controlled-Phase gates between the qubits at the ends

of the edge. Cluster state used for MBQC is generated

before the computation starts. Ideally, we want all mea-

surements on the qubits of the cluster state to result in

+1 eigenvalues to implement the right computation. If

the measured eigenvalue is -1 due to the randomness of

quantum measurements, the computation is corrected by

applying Pauli corrections, i.e. rotating the measurement

basis of the following measurements. The subsequent

measurements depend upon the measurement results of

the previous measurements. Fig. 1 shows a quantum

circuit on the left and on the right is the MBQC im-

plementation of that circuit on a 3x7 2D cluster state.

arXiv:2210.11465v1 [quant-ph] 20 Oct 2022

Here, we have two types of qubits - the quantum cir-

cuit qubits and cluster state qubits. In MBQC, each

quantum gate on the quantum circuit qubits can be de-

composed into a series of measurements on cluster state

qubits. In Fig. 1(b), the highlighted qubits are mea-

sured and diﬀerent colors are for diﬀerent measurement

basis. The measured cluster state qubits are highlighted

in the same color as the quantum gate in Fig. 1(a) their

measurement implements. The green highlight signiﬁes

Pauli-Z basis measurement. Pauli-Z basis measurement

removes the measured qubit from the cluster state. It is

essential to perform these measurements to isolate cluster

qubits that undergo single qubit operations on diﬀerent

quantum circuit qubits from each other. At the end of

the measurements, the state of the two unmeasured clus-

ter qubits or output qubits in Fig. 1(b) should match the

state of qubit Q1, Q2in Fig. 1(a).

As seen from Fig. 1(b)-(c), translating a quantum cir-

cuit to a series of measurements on a cluster state in

MBQC can be seen as a tiling puzzle where a set of

blocks are to be arranged on a lattice with the same ge-

ometry as the cluster state. For example, in the case

of a square-grid cluster state, the measurement blocks

take the shape of polyominos, commonly known as puzzle

blocks for games like Tetras. In this paper, we have de-

signed a tiling puzzle to map quantum circuits to MBQC

measurement patterns that closely resemble the game of

Tangram. Our puzzle is slightly diﬀerent in the sense

that it asks the player to replicate a quantum circuit us-

ing polyominos that signify MBQC measurement blocks

and while arranging the polyominos the player needs to

follow speciﬁc rules dictated by MBQC. Note that, the

measurement pattern for a quantum gate is not unique,

which makes our puzzle interesting and challenging. Ad-

ditionally, the player is scored based on the total area

covered by polyominos such that minimizing this area is

encouraged.

We ﬁrst describe the game in detail in Section III. We

then give the reasoning behind the game rules using the

MBQC theory in Section IV.

III. QUANTUM TANGRAM

This section describes the game in terms of the inter-

face and the MBQC principles translated into the rules

the players needs to follow while placing polyominos.

A. The gameplay

When the game starts, we give the player an interactive

tutorial on how to create equivalent polyominos based on

Section IV A. As part of the game, the player is given

a quantum circuit, an empty square-grid to add poly-

omionos. In the current version of our game, the player

is given only Cliﬀord quantum circuits. All Cliﬀord quan-

tum circuit operations can be performed using only Pauli

basis measurements on the cluster state. The Pauli-X, Y

and Z basis measurements are represented as blue, orange

and green monominos, respectively as shown in Fig. 2.

These monominos are used to generate every other poly-

omino in our game. Having only three colors for the poly-

ominos keeps the game simple. Fig. 3 shows the minimal

polyominos, i.e., the measurement blocks with least num-

ber of measurements for quantum gates for the Cliﬀord

gates and the SWAP gate [1–3]. The player has inﬁnite

supply of minimal polyominos for wires (identity gate)

(see Fig. 4), the Cliﬀord gates, the SWAP gate along

with the monominos for the Pauli measurements. Fig. 5

shows various stages of the game. Note that, the given

polyominos implement the corresponding quantum gate

modulo some phase which comes from the probabilistic

measurement outcomes. Here, we ignore that phase for

the sake of simplicity. The player can drag and drop, ro-

tate the given polyominos, and append wires to deform

the polyominos using the rules discussed in Section III B.

To further simplify the game, we paint every square on

the grid green corresponding to Pauli-Z measurements

to start with. When the player puts a polyomino on

the grid, the squares get re-colored with the colors from

the polyomino. This ensures that every polyomino is ap-

propriately padded with Pauli-Z measurements and the

player won’t have to add the green tiles manually. We

also ask the player to mark the positions of the output

qubits. This is required to evaluate their submission as

discussed in Section IV B. While evaluating the submis-

sion, we ﬁrst check for correctness and score the correct

solutions that consume lesser area higher. If the player

replicates the quantum circuit, they move on to the next

more diﬃcult level.

B. Game rules

In this section, we describe the game rules as they

would appear in the actual game, designed such that

no prior knowledge of quantum information is required

to understand them. We refer to polyominos as puzzle

blocks and the monominoes (squares) of a polyomino as

tiles in this section. The goal is to implement the given

quantum circuit while minimizing the area occupied by

the non-green tiles.

Rule 1: Start reading the given quantum circuit from

left to right. Each gate in the quantum circuit corre-

sponds to a puzzle block given to you. You can drag and

drop the puzzle blocks for the gates onto the game-board

area to implement the quantum circuit.

Rule 2: A puzzle block can be deformed or its shape can

be modiﬁed without changing its function, if every tile in

the new modiﬁed puzzle block has the same non-green

tile neighborhood has the original block.

Rule 3: All puzzle blocks have ‘In’ and ‘Out’ tiles

marked on them. The numbers of In- and Out-tiles of

a block are each equal to the number of qubits the cor-

reponding quantum gate operates on. You can place the

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Measurement-basedQuantumComputationasaTangramPuzzleAshleshaPatil,1,YosefP.Jacobson,2DonTowsley,3andSaikatGuha11WyantCollegeofOpticalSciences,UniversityofArizona,TucsonAZUSA2DepartmentofComputerScience,UniversityofArizona,TucsonAZUSA3CollegeofInformationandComputerSciences,UniversityofMassachusetts,...

展开>> 收起<<

Measurement-based Quantum Computation as a Tangram Puzzle Ashlesha Patil1Yosef P. Jacobson2Don Towsley3and Saikat Guha1 1Wyant College of Optical Sciences University of Arizona Tucson AZ USA.pdf

共7页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Measurement-based Quantum Computation as a Tangram Puzzle Ashlesha Patil1Yosef P. Jacobson2Don Towsley3and Saikat Guha1 1Wyant College of Optical Sciences University of Arizona Tucson AZ USA

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: