# Determination of the helpfulness of physics exam study methods

Rahul Jilakara and David P. Waters
Department of Basic Sciences, University of Health Sciences and Pharmacy
St. Louis, Missouri 63110, USA

###### Abstract

Studying for physics exams can be difficult and stressful, especially during a
student’s introductory year in physics. For students who do not plan to major
in physics, the desire to do well is based less on understanding concepts and
more on achieving a better grade. For this reason, students want to study as
efficiently as possible by using the most optimal study methods. We have taken
surveys over the past three years to determine how students study for exams
and compared that to their exam grades. We found that students who studied
using methods that they rated as more helpful did better on the exams. By
utilizing the study results, we are able to present our current and future
students with study methods that have been rated as being more helpful, and
give them advice on ways to optimize their study time for exams.

##  1 BACKGROUND

As we prepare this study, we recognize that the information gathered was based
on self-report and Likert-type instruments. Self-report means that a student
provides their own ratings instead of using an independent determination, and
these have both advantages and disadvantages [1, 2, 3]. The advantages of
self-reports are that we do not interrupt or influence someone during their
process, and it allows us to collect a lot of data relatively easily.
Unfortunately, students may not be able to accurately recall everything, or
may be biased in their answers [4]. Althubaiti et al. have looked at the
information bias in health research using self-reporting, and have found that
recognizing these biases can help to lessen the effects [5].

Study habits are important for college students, and not all students know how
to study in an optimal manner [6]. For example, research has been conducted on
how best to study for exams in medical school [7], which looked at the testing
effect, active recall, and spaced repetition, which are all examples of study
skills. In our study, we will be looking at study methods that come from
preparing for physics examinations during introductory algebra-based physics
courses. We define study methods as the materials that students use to study
for exams.

It would be ideal if there were a set of universally helpful study methods
that we could provide to our students. Unfortunately, research has shown that
different students may use this information more or less successfully. For
example, high-achieving students have been found to better prepare for exams
by using study methods that are more helpful [8, 9, 10, 11] while low-
achieving students used the order of materials to determine what they would
need to study [12]. An interesting finding is that some low-achieving students
would recommend more helpful study strategies - a combination of study skills
and study methods - to others, but then would use less effective study
strategies for themselves [12]. These students often would not use more
effective strategies because of a lack of time or motivation [13]. These
findings show why a student would continue to use a study method that they
continuously rated as less helpful. It is also possible that a student’s
ability to recognize whether something was helpful could be biased [14].

Previous work on study strategies for exam preparation has found that
providing information about how to study can be more useful than providing the
exact questions on the exam [14]. The authors found that distributing efforts
across many study methods can help in preparing for an exam. Also, they found
that knowing the format of the exam can be helpful for students. For this
reason, our physics courses provide last year’s exam to students, in order to
both show the format of the exam and give students material to prepare for the
exam. Fakcharoenphol et al. find that studying using old exam practice
problems can help, although learning may be shallow [15]. Since our exams come
right after studying, we do not know if the learning that brought about higher
exam scores was salient. Previous research also determined that studying on
their own using worked-out solutions – old exams and class slides (problems) –
and targeted exercises such as the review problems allowed students to perform
better than they did when using traditional study methods, such as rereading
the textbook [16]. Finally, completing web-based physics homework problems can
lead to higher overall exam performance [17], so using these homework problems
to study may also help students improve their exam scores.

Although many study methods can improve a student’s exam scores, some study
methods have been found to be less helpful. Although students believed that
reading the textbook in order to study for an exam improved their
understanding, doing so had no effect on their exam performance because it
gave them a false sense of understanding [18]. This finding is interesting
because many studies that look at exam preparation only have textbook readings
as their study method [19]. Pressley et al. determines strategies to use
textbook reading successfully, which may explain why some of our students
label textbook reading as helpful.

It has been found that students must adapt their study method to the type of
task that they are expected to complete [20], so a study method that results
in better exam grades for most students may not be as helpful in another
environment. It may be difficult to make a list of helpful study methods from
our physics courses and implement them in other environments. One would expect
that some study methods would be more helpful than others. Some students are
going to learn better from certain study methods while others will not learn
as well using the same study methods [19]. This may explain why study methods
in our courses work better for some students than for others. Assuming that
our students’ self-reporting is accurate, it may be that students use the
study methods differently or that they begin the preparation with different
levels of understanding, and thus will need to use different methods.

##  2 PROCEDURE

###  2.1 Population

The survey was given to undergraduate students, mostly sophomores and juniors,
at the University of Health Science and Pharmacy in St. Louis. The courses in
the fall and spring were algebra-based introductory physics courses. These
courses were required for health science majors who were most often going to
enter the pharmacy program or take a health science professional exam such as
the MCAT. The fall and spring courses each had a typical enrollment of 60-80
students.

###  2.2 Data Collection

After each exam, students were asked to fill out a survey. These surveys were
administered using the course’s LMS (Moodle). The surveys were available to
all students, but participation was voluntary.

The survey questions are listed below:

  * •

Q1: Approximately how many hours did you study for the exam?

  * •

Q2: What percentage of time did you use the following materials to study for
the exam? (10%, 20%, etc. and N/A)

  * •

Q3: How helpful were these material types for the exam? (Scale: 1 = least
helpful and 5 = most helpful)

Any student who did not use a certain study method answered N/A on Q2 and Q3
for that study method. Some students did not choose N/A for Q3 for a study
method that they did not use, so we changed that Q3 value to an N/A for them.

A list of the study methods available along with an explanation of each was
given:

  * •

Rereading Textbook \- The course uses OpenStax College Physics Textbook [21].
Sections of the textbook are given as a smaller PDF before each class. The
assumption is that students read the textbook before class, so this method
would involve reading the textbook again before the exam.

  * •

Class Slides (Conceptual) \- During each class, students are asked multiple
choice questions and use a clicker to input the answer. These questions are
conceptual in nature, meaning that there usually is not any math needed to
answer them. They are similar to the multiple choice questions on the exam.

  * •

Class Slides (Problems) \- Each week, after the topics have been introduced
and discussed, students are given a day to work only on mathematical problems
in class. These problems are similar to the mathematical problems that
students will see on the exam. Worked-out solutions are provided.

  * •

Review Questions \- Review questions are posted for the students to work on.
These involve multiple choice questions that may be either conceptual or
mathematical in nature. These are all new questions that have not been seen
before. The answers are provided, but the solutions are not. For AY 2017-2018,
the questions were on our LMS, but the number of questions was limited. For AY
2018-2019, these questions were posted externally with more questions added.
In AY 2019-2020, these questions were posted on the course’s LMS page with
many more questions available.

  * •

Old Exam \- The previous year’s exam is provided as a study method, both to
give insight about the format of the exam as well as to provide more practice
opportunities. The answers are provided.

  * •

Homework Problems \- Homework assignments involve solving mathematical
problems similar to those seen in class and those on the exam.

  * •

Reading quizzes \- Before each class, students are asked a series of questions
to see if they have read the textbook and/or watched the video. These are
simple questions to check for a basic understanding of the pre-class material.

###  2.3 Course Exams

The course exams were made up of conceptual (multiple-choice) questions and
mathematical problems. These were paper exams on which students would write
out their work. For the multiple choice questions, students could write out
their work for partial credit. The mathematical problems also allowed for
partial credit, with the bulk of the points awarded for showing how to solve
the problem. All exam scores included in the data are after partial credit was
given. Exams usually had about 10 MC questions worth 3-4 points each and 3-4
problems with individual parts that made up more than half of the grade. For
our analysis, we include the overall grade for the exam as well as scores for
the conceptual section and scores for the problems section. This separation
allowed us to compare study methods that focused on concepts versus study
methods that required mathematical solutions.

##  3 Study Method Usage

###  3.1 Data Analysis

The collected data from the student-filled surveys was divided and analyzed
according to the semester it was collected. For each semester, we determined
the average amount of time that a student studied for each particular exam
from Q1. Likewise, using the data from Q2, we averaged the percent of time
that each student spent utilizing each of the seven study habits per exam over
the course of the semester.

Next, we took the percent of time spent on each study method from each
semester and averaged it all together to produce the percent of time spent on
each study method for the overall collected data. The percent of time spent
per each study method was then multiplied by the average amount of time spent
studying (Q1*Q2) to produce the average time spent on each study method for
the overall data.

###  3.2 Results

To determine the overall effectiveness and use of each study method, we
compared the different graphs produced. As seen in Figure 1, on average,
students spent a majority percentage of time studying using class slides
(problems), old exams, and class slides (conceptual). The average amount of
time that students spent rereading the textbook was surprisingly small.

Figure 1: Average percentage of time spent studying. The average percentage of
time that students spent on each study method. Out of the 7 study methods,
students spent the least percentage of their overall study time on rereading
the textbook and reading quizzes. The most popular study methods were class
slides (problems), class slides (conceptual), and old exams.

The graph for average percentage of time studying (Figure 1) was produced with
the averaged data. Although we calculated the total time spent by multiplying
the total time that each student spent studying by the percentage that each
study method was used (Q1*Q2), the graph looked nearly identical to Figure 1,
so we did not include the graph for the total time spent on each study method.
Also, when we discuss comparisons, we find that the correlation results are
similar for both the percentage of time and the total time spent on each study
method.

A lingering question throughout this study is whether, if students know they
will be asked about their study methods (which they realize after the first
exam in the fall semester), this has an effect on how they prepare for
subsequent exams.

##  4 Study Method Helpfulness

###  4.1 Data Analysis

The perceived helpfulness of each study method per exam per semester from Q3
was averaged. This was done in a similar method to how the average total
amount of time that each student spent studying for each exam was calculated.
Then, the helpfulness of each study method for every semester was averaged to
find the overall average perceived helpfulness for each study method. We also
took the average of the helpfulness rating for all of the study methods over
all of the exams throughout all of the semesters. This process gave us an
overall average helpfulness rating.

We used grouping of study methods to compare how students could have studied.
Study methods that were more helpful were grouped together, as were study
methods that were less helpful. During data collection, only those students
who marked that they had used a certain study method in Q2 also recorded the
helpfulness of that study method in Q3. Students who did not use a study
method did not include a helpfulness rating. This means that if a study method
had a low helpfulness rating, that was because the students who used that
method had rated it poorly. We are assuming, although we have no evidence,
that those who did not use a study method chose to ignore this option because
they decided it would not have been helpful, and thus rarely used study
methods probably would have had an even lower helpfulness rating if all
respondents had been asked to rate the helpfulness of all study methods.

We used three different ways to determine whether a study method was helpful
or unhelpful. The first was to look at how students individually rated the
helpfulness of study methods. The second was to look at how students rated the
helpfulness of study methods each semester on average. The third way was to
create groups of universally helpful and unhelpful study methods.

For individual helpfulness (individual), we compare how a student rated each
study method for that exam to the overall average helpfulness rating. A study
method is considered helpful to that student if they rated the study method as
higher than the overall average, and vice versa. In this case, we cannot
create separate groups for study methods that are helpful vs. unhelpful
because each student had a different interpretation of which study methods
were helpful for them.

For average helpfulness (average), if a study method for a specific exam in a
specific semester received an average helpfulness that was greater than the
overall average, then that study method was determined to be helpful and was
placed in the helpfulness group. Similarly, the unhelpful study methods
received less than the overall average helpfulness rating. In this case, the
helpful and unhelpful study methods were the same for all students.

For helpfulness groups (group), any study method that was more helpful than
this overall helpfulness rating after averaging all of the semesters together
was labeled helpful, and any method that had a lower-than-average helpfulness
was labeled unhelpful.

###  4.2 Results

To determine the overall average, we took all of the helpfulness ratings for
every study method used by every student for every exam in every semester and
averaged all of these to obtain an overall helpfulness rating. The overall
helpfulness rating (OHR) was 3.44 out of a total of 5. Any study method that
was rated higher than this value was determined to be helpful for that student
(individual) or during that exam (average) or overall (group). In order to
recognize if a study method was helpful or unhelpful overall, we can look at
Figure 2 to determine the overall helpfulness of each study method, which uses
the averages from Q3. The horizontal black line represents the overall
helpfulness rating. We can see that class slides (both types), the old exams,
and homework problems were all higher than the OHR. These study methods are
considered helpful to most students and, are placed in the helpful group in
this paper. On the other hand, rereading the textbook and reading quizzes had
an overall helpfulness that was lower than the OHR, are considered less
helpful to most students, and are placed in the unhelpful group.

Figure 2: Study Method Helpfulness. The helpfulness rating for each study
method averaged over every exam in every semester. The horizontal black line
represents the overall helpfulness rating. Of the 7 study methods, four are
clearly above the overall helpfulness rating of 3.44 and two are clearly
below. This demarcation allows us to designate these study methods into
helpful and unhelpful groups. Review questions is at the overall helpfulness
rating and is not included into either designation.

To get an idea of how the study methods’ helpfulness changes throughout each
semester, we can look at Figure 3, in which the data was made into a line
graph to help demonstrate the different helpfulness for each study method
throughout each semester. Once again, a horizontal black line is provided as a
guide to represent the OHR. We can see that for the most part, a study method
that starts off as helpful remains that way. The only study method that does
not follow this rule is review questions. This could be because many more
questions were added to the review questions each year and improvements were
made to these questions. Because review questions shifted throughout the
semesters, as seen in Figure 3, it cannot be designated as always helpful or
unhelpful.

Figure 3: Study Method Helpfulness for semester. Each series indicates how a
study method changed throughout the 6 semesters. To determine these values,
all of the helpfulness ratings for each student and each exam throughout the
semester are averaged together.

The Average Helpfulness graphs, both the bar graph (Figure 2) as well as the
line graph (Figure 3), indicate the perceived helpfulness of each study
method. Class slides (conceptual) and class slides (problems) seemed to be
deemed the most helpful when preparing for an exam. Both of these study
methods received the highest rating of all the different study methods; 4 out
of 5. Those that used rereading textbook as a study method did not find that
study method to be as helpful to their performance on an exam compared to the
other study methods. This observation can be strengthened by Figure 3, which
indicates a downward trend of ratings of helpfulness from the first semester
that this survey was administered to its last. Comparing the average time that
students spent on each study method as well as the students’ perception of the
helpfulness of each study method helped us understand the potential impact of
each study method.

Comparing Figure 1 with Figure 2, we find that students spend more time using
study methods that most of the class believed are helpful. Perhaps
unsurprisingly, the most helpful study methods are ones that involve questions
and problems that are similar to exam questions and problems. In the next
section, we compare the effect that relying more on the helpful study methods
had on exam grades.

##  5 Comparisons

###  5.1 Data Analysis

To determine how the use of each study method correlated with exam grades, we
wrote a program in R that calculated the correlation value and the
significance of this correlation. We used the rcorr function in R using the
Pearson correlation method. The inputs were the groups of study methods and
the exam grades.

The three different helpfulness categories were the individual helpful and
unhelpful study methods (individual), the average helpfulness (average), and
the grouping of study methods into helpful and unhelpful (group). These
groupings allowed us to compare the grades of students who spent more of their
study time using the 4 helpful study methods and those who relied more on the
two unhelpful study methods. As a reminder, the groupings were as follows:

  * •

Helpful Study Methods

    * –

Class Slides (Conceptual)

    * –

Class Slides (Problems)

    * –

Old Exam

    * –

Homework Problems

  * •

Unhelpful Study Methods

    * –

Rereading Textbook

    * –

Reading Quizzes

The study method labeled as helpful for one student (individual) or one exam
(average) may not be labeled as helpful every time. Figure 3 offers an
overview of the helpfulness of each study method in a specific semester. For
the groupings, the same study methods are labeled helpful or unhelpful for all
exams.

We broke the exam grades into three categories. First, we used the overall
exam averages. Because the exams were split between mathematical problems and
conceptual questions, we further broke the exam grades out into problems (2nd
category) and conceptual (3rd category).

All reported correlations have a significance of p¡0.05. If a value from the
correlation table had a p-value of greater than or equal to 0.05, we did not
include that value in our results. If a value included a significance of more
than one star, then 2 stars represents p¡0.01 and 3 stars represents p¡0.001.
Since there were 21 exams during the 6 semesters in which data was collected,
we will be discussing the correlations that show up in many of the exams.

###  5.2 Results

To determine if there was a correlation, we did not look at only one exam or
only one semester, we looked at every exam from every semester. For the
individual helpfulness rating, significant correlations showed up in 13 of the
21 exams. For the average helpfulness, significant correlations showed up in 7
of the exams. For the groupings, significant correlations showed up in 11 of
the exams. We concluded from this that there is strong evidence that
individual helpfulness correlates with exam grades, there is evidence that
there is a correlation between helpfulness groups and exam grades, and there
is weaker evidence that there is a correlation between average helpfulness and
exam grades.

An example of correlation data that shows this relationship is shown in Figure
4. These tables represent only 2 of the 21 exams, but they are indicative of
the strong correlations that we find between using helpful study methods and
exam grades. We see in Exam 1 that there is a significant positive correlation
for individual helpfulness (individual) across all overall exam grades and
exam grades from problems. These correlations indicate that when a student
spent a greater percentage of their time on study methods that they labeled as
more helpful than the OHR, the student’s grades were higher. Exam 1 also shows
a significant negative correlation between spending more time on individually
unhelpful study methods and exam grades, which means students’ exam grades
were lower after using less helpful study methods. We see in Exam 4 that there
are significant correlations for average helpfulness (average) and helpfulness
groupings (group) for both overall exam grades and the grades for mathematical
problems. We did not include conceptual grades in these examples because there
were fewer correlations.

Figure 4: Correlation table example from the first exam in the fall of 2019
and fourth exam in the fall of 2017 showing that there were significant
correlations between individual helpfulness and average helpfulness ratings
and exam grades. Stars represent the level of significance and blank spaces
represent correlations that were not significant. Exam grades are broken down
further into the grades for the mathematical problems and the conceptual
questions.

exams by spending more time on study methods that they rated as more helpful
and less time on study methods that they rated as unhelpful (individual) had
higher grades on their exams. Students who spent more time on study methods
that they labeled as unhelpful and less time on study methods that they
labeled as helpful had lower exam grades.

A similar result is found for students who studied for exams by spending more
time on helpful study methods (group). An example of these correlations is
shown in Exam 4 of Figure 4. Exam 4 is only a single example, but it is
indicative of the evidence that we find. We see that there is a significant
positive correlation between using study methods that are labeled on average
as more helpful and the overall exam grades and the grades from problems. We
did not see as many correlations between using helpful study methods and the
grades on the conceptual parts of the exam, so this was not included in the
table.

Although weaker, there is some evidence that students who spend more time on
study methods labeled as helpful for that exam (average) earned higher exam
grades. Examples of these correlations are shown in Exams 1 and 4 of the table
in Figure 4. Because this is weaker, it is possible that study methods may be
rated differently for each exam, despite their overall helpfulness not
changing much.

By combining all three methods (individual, average, and group), we find
significant correlations between studying using helpful study methods and exam
grades on all but 6 of the 21 exams. These exams are spread over fall and
spring and over each of the exams, so there is not anything specific that we
can point to explaining why some exams did not show any significant
correlations.

##  6 DISCUSSION

We find a positive correlation between the time spent studying using study
methods that an individual student labeled as helpful (individual) and higher
exam grades. We also find a positive correlation between the time spent using
helpful study methods (group) and higher exam grades. When students study for
exams using more helpful study methods, they end up doing better on their
exams. Unfortunately, the definition of what makes a study method helpful for
each student is difficult to determine. The helpful group suggests that we
could provide future students with information about the helpful and unhelpful
study methods. We could imagine that providing a suggestion of what material
will be most helpful in studying for exams might help students to improve
their exam scores, especially those who may not be as good at differentiating
which study methods are helpful. On the other hand, the evidence from
individual helpfulness suggests that students who study what they determine to
be helpful have higher grades, and vice versa. For this reason, providing the
average helpfulness ratings could actually hinder a student who finds
something helpful that others did not.

After finding evidence that students who study using more helpful study
methods do better on their exams, we wonder about the causal relationship. Is
this due to the fact that some students are better at choosing helpful study
methods? Are they better at recognizing what was most helpful for them or did
the study methods themselves help the students? Answering these question is
the key to truly understanding what these results mean and what to do with
them. For this reason, further research will be needed. One possibility would
be to provide information about the helpful group of study method (group) to
one group of students and not to a control group. We could track whether
having this information had an effect on their choice of study methods and
their exam grades. While we were hoping to come away from this project with a
definitive list of helpful study methods to disseminate to current and future
students, we recognize that more research is needed.

## References

  * [1] G. Schellings, B. van Hout-Wolters, Measuring strategy use with self-report instruments: Theoretical and empirical considerations. Metacognition and Learning. 6, 83–90 (2011).
  * [2] B. Van Hout-Wolters, G. Schellings, Measuring learning strategies. Kinds of measurement methods and their usefulness in educational research and practice. Pedagogische Studien. 86, 110–129 (2009).
  * [3] Veenman, M. V. J. (2011). Learning to self-monitor and self-regulate. In R. Mayer and P. Alexander (Eds.),Handbook of research on learning and instruction (pp. 197–218). New York: Routledge.
  * [4] Veenman, M. V. J. (2005). The assessment of metacognitive skills: What can be learned from multimethod designs? In C. Artelt and B. Moschner (Eds.), Lernstrategien und Metakognition: Implikationen fürForschung und Praxis (pp. 75–97). Berlin: Waxmann.
  * [5] A. Althubaiti, Information bias in health research: Definition, pitfalls, and adjustment methods. Journal of Multidisciplinary Healthcare. 9 (2016), pp. 211–217.
  * [6] S. Kumar, Study Habits Of Undergraduate Students. International Journal of Education and Information Studies. 5, 17–24 (2015).
  * [7] M. Augustin, How to learn effectively in medical school: Test yourself, learn actively, and repeat in intervals. Yale Journal of Biology and Medicine. 87, 207–212 (2014).
  * [8] A. Kitsantas, Test preparation and performance: A self-regulatory analysis. Journal of Experimental Education. 70, 101–113 (2002).
  * [9] Pintrich, P. R., and Schunk, D. H. (2002). Motivation in education: Theory, research, and application. Upper Saddle River, NJ: Prentice-Hall.
  * [10] D. L. Sundre, A. Kitsantas, An exploration of the psychology of the examinee: Can examinee self-regulation and test-talking motivation predict consequential and non-consequential test performance? Contemporary Educational Psychology. 29, 6–26 (2004).
  * [11] C. VanZile-Tamsen, J. A. Livingston, The differential impact of motivation on the self-regulated strategy use of high- and low-achieving college students. Journal of College Student Development. 40, 54–60 (1999).
  * [12] J. P. Holschuh, Do as i say, Not as i do: High, Average, and Low-performing students’ Strategy use in biology. Journal of College Reading and Learning. 31, 94–108 (2000).
  * [13] J. E. Barnett, Self-regulated reading and test preparation among college students. Journal of College Reading and Learning. 31, 42–53 (2000).
  * [14] S. Van Etten, G. Freebern, M. Pressley, College students’ beliefs about exam preparation. Contemporary Educational Psychology. 22, 192–212 (1997).
  * [15] W. Fakcharoenphol, E. Potter, T. Stelzer, What students learn when studying physics practice exam problems. Physical Review Special Topics - Physics Education Research. 7 (2011).
  * [16] W. Fakcharoenphol, T. Stelzer, Physics exam preparation: A comparison of three methods. Physical Review Special Topics - Physics Education Research. 10 (2014).
  * [17] R. Dufresne, J. Mestre, D. M. Hart, K. A. Rath, The Effect of Web-Based Homework on Test Performance in Large Enrollment Introductory Physics Courses. Jl. of Computers in Mathematics and Science Teaching. 21, 229–251 (2002).
  * [18] T. Linderholm, A. Wilde, College students’ beliefs about comprehension when reading for different purposes. Journal of College Reading and Learning. 40, 7–19 (2010).
  * [19] M. Pressley, L. Yokoi, P. Van Meter, S. Van Etten, G. Freebern, Some of the Reasons Why Preparing for Exams Is so Hard: What Can Be Done to Make It Easier? Educational Psychology Review. 9, 1–38 (1997).
  * [20] H. Broekkamp, B. H. A. M. Van Hout-Wolters, Students’ adaptation of study strategies when preparing for classroom tests. Educational Psychology Review. 19, 401–428 (2007).
  * [21] OpenStax College. (2012). College Physics. OpenStax. https://openstax.org/details/books/college-physics


# Classical Processing Requirements for a Topological Quantum Computing
System.

Simon J. Devitt<EMAIL_ADDRESS>National Institute of Informatics, 2-1-2
Hitotsubashi, Chiyoda-ku, Tokyo-to 101-8430, Japan  Austin G. Fowler  Center
for Quantum Computing Technology, University of Melbourne, Victoria 3010,
Australia  Todd Tilma  National Institute of Informatics, 2-1-2 Hitotsubashi,
Chiyoda-ku, Tokyo-to 101-8430, Japan  W. J. Munro  Hewlett Packard
Laboratories, Bristol BS34 8HZ, United Kingdom  National Institute of
Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo-to 101-8430, Japan  Kae
Nemoto  National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku,
Tokyo-to 101-8430, Japan

###### Abstract

Dedicated research into the design and construction of a large scale Quantum
Information Processing (QIP) system is a complicated task. The design of an
experimentally feasible quantum processor must draw upon results in multiple
fields; from experimental efforts in system control and fabrication through to
far more abstract areas such as quantum algorithms and error correction.
Recently, the adaptation of topological coding models to physical systems in
optics has illustrated a possible long term pathway to truly large scale QIP.
As the topological model has well defined protocols for Quantum Error
Correction (QEC) built in as part of its construction, a more grounded
analysis of the classical processing requirements is possible. In this paper
we analyze the requirements for a classical processing system, designed
specifically for the topological cluster state model. We demonstrate that via
extensive parallelization, the construction of a classical “front-end” system
capable of processing error correction data for a large topological computer
is possible today.

###### pacs:

03.67.Lx, 07.05.Wr

##  I Introduction

The design and construction of a feasible large scale quantum computing system
has been a highly sought after and long term goal of quantum information
science ever since the first physical system proposals were made in the mid
1990’s Cirac and Zoller (1995); Cory et al. (1997); Gershenfeld and Chuang
(1997); Kane (1998); Loss and DiVincenzo (1998); Knill et al. (2001); Mooij et
al. (1999); Nakamura et al. (1999); ARDA (2004); Kok et al. (2007). While
experimental advances in quantum computing have been pronounced Chiorescu et
al. (2003); Yamamoto et al. (2003); Chiaverini et al. (2004); Häffner et al.
(2005); Gorman et al. (2005); Gaebel et al. (2006); Hanson et al. (2006); Dutt
et al. (2007); O’Brien et al. (2003) we are not yet at the stage where we can
faithfully claim a multi-million qubit device is just around the corner.

Nevertheless, in order for experimental progress to be made, the fundamental
theoretical building blocks for a large scale computer need to be firmly in
place. This theoretical development is not restricted to the discovery of new
protocols for computation, algorithms or error correction but it also includes
the architectural engineering of future computers.

While there has been steady progress over the past 15 years on designing novel
and (more importantly) experimentally feasible large scale processor
architectures, the complication of implementing appropriate and efficient
error correction procedures and designing systems which can trivially be
scaled to the level of a “programmable”, multi-task computer is still a
daunting and often neglected area of research.

Recently, the introduction of theoretical ideas such as topological cluster
state quantum computing (TCQC) Raussendorf et al. (2007); Raussendorf and
Harrington (2007); Fowler and Goyal (2009) and the single photon optical
architecture Devitt et al. (2009); Ionicioiu and Munro (2009) gives us an idea
of what a truly large scale device may possibly look like. The modular design
of the cluster preparation network, and the measurement based nature of the
computational model, gives this design something that other architectures
arguably lack, a strictly modular scaling of the entire computer.

While the design introduced in Refs. Devitt et al. (2009, 2008) is not
necessarily the optimal way to construct a large scale quantum computer, it
does contain several key elements, easing the conceptual design of a large
scale computer. For example:

  1. 1.

Utilizing a computational model that is fundamentally constructed from error
correction, rather than the implementation of codes on top of an otherwise
independent computational model.

  2. 2.

Having a modular construction to the computer. The fundamental quantum
component (the photonic chip Stephens et al. (2008); Devitt et al. (2009)), is
a comparatively simple quantum device. Scaling the computer arbitrarily
requires the addition of more chips in a regular and known manner.

  3. 3.

Employing a computational model exhibiting high fault-tolerance thresholds
Raussendorf et al. (2007), which relieves the pressure on experimental
fabrication and control.

  4. 4.

Utilizing a measurement based model for computation Raussendorf and Briegel
(2001). By employing a measurement based computational model, the quantum
component of the computer is a simple state preparation network. Therefore,
programming such a device is a problem of classical software, not of hardware.

These properties, as well as others, allowed us to consider the structure of
an extremely large mainframe-type device. In Ref. Devitt et al. (2008), the
quantum analogue of high performance computing was examined. The conceptual
scalability of the optical architecture allowed us to examine the operating
conditions, physical structure and resource costs of a computer employing
extensive topological error correction to the level of 2.5 million logical
qubits.

In addition to examining the implementation of a large scale TCQC, the nature
of the topological model also allows for a more concrete discussion on an
often neglected, but important aspect of quantum information processing,
namely what are the classical computational requirements of a large scale
device? In this paper we attempt to answer this question.

There have been several broad investigations into the classical structure,
design and operation of a large scale quantum computer Meter (2006); Steane
(2007), but investigation into this topic is difficult. The primary obstacle
in analyzing classical requirements is that the quantum architecture generally
has to be specified. Since all classical processing is ultimately dependent on
both the computational model employed at the quantum level and more
importantly the error correction protocols utilized, a detailed analysis of
the classical front end must wait for the design of the quantum processor.

In this paper we specifically analyze the classical front end requirements to
perform active error correction on a 3D topological cluster lattice prepared
by the photonic chip network. This analysis will be restricted to the
classical system required to implement the underlying error correction
procedures in the topological model, without the execution of an active
quantum algorithm.

Although we present this analysis in the context of the optical network
presented in Ref. Devitt et al. (2009), it should be stressed that this
analysis is still highly relevant for any physical architecture employing the
2D or 3D topological model Bravyi and Kitaev (2001); Dennis et al. (2002);
Raussendorf and Harrington (2007); Raussendorf et al. (2007); Fowler et al.
(2008). Our analysis demonstrates that with several optimizations of the
classical processing and the ability to significantly parallelize classical
error correction processing, the classical computational requirements for
large scale TCQC are indeed within the capabilities of today’s processing
technology.

Section II very briefly reviews the nature of the topological cluster model in
order to fully specify what is required of the classical processing. Section
III reviews the flowing nature of the preparation network, and how this
relates to the optical measurement layer, and the first level of classical
processing. In Section IV we overview the basic requirements of the classical
network and how target processing rates are related to the clock cycle of the
quantum network. In Section V we introduce classical benchmarking data for the
minimum weight matching algorithm utilized for error correction and
illustrate, given this data, how error correction processing can be
parallelized over the entire computer. We conclude by illustrating how the
parallelization of the classical processing allows, in principal, for the
construction of a classical error correcting front end for large scale TCQC
with classical processing technology available today.

##  II Topological Error Correction in the Optical Architecture

TCQC was first introduced by Raussendorf, Harrington and Goyal in 2007
Raussendorf and Harrington (2007); Raussendorf et al. (2007). This model
incorporates the ideas stemming from topological quantum computing introduced
by Kitaev Kitaev (1997) and cluster state computation Raussendorf and Briegel
(2001), leading to a very attractive computational model incorporating error
correction by construction and exhibiting a high threshold error rate.

As with any measurement based computational model, computation proceeds via
the initial construction of a highly entangled multi-qubit state. Fig. 1
illustrates the structure of the cluster. Each node in the cluster represents
a physical qubit, initially prepared in the
${|{+}\rangle}=({|{0}\rangle}+{|{1}\rangle})/\sqrt{2}$ state, and each edge
represents a controlled-$\sigma_{z}$ entangling gate between qubits. This is
the fundamental unit cell of the cluster, which repeats in all three
dimensions.

Computation under this model is achieved via the consumption of the cluster
along one of the three spatial dimensions Fowler and Goyal (2009) (simulated
time). Logical qubits are defined via the creation of “holes” or “defects”
within the global lattice and multi-qubit operations are achieved via braiding
(movement of these defects around one another) as the cluster is consumed
along the direction of simulated time. The specific details for computation
under this model are not important for this discussion and we encourage the
reader to refer to Refs. Raussendorf et al. (2007); Fowler and Goyal (2009)
for further details. For this analysis, the effect of errors on a topological
lattice is the important factor.

###  II.1 Error effects

Quantum errors in this model manifest in a very specific way. In Fig. 1,
illustrating the unit cell of the cluster, we have illustrated six face qubits
shown in red. If no errors are present in the system, measuring each of these
six qubits in the ${|{+}\rangle}$ or ${|{-}\rangle}$ states ($\sigma_{x}$
basis) will return an even parity result. If we denote the classical result of
these six measurements as $s_{i}\in\\{0,1\\}$, $i=1,..,6$, then

$(s_{1}+s_{2}+s_{3}+s_{4}+s_{5}+s_{6})\text{ mod }2=0.$ (1)

Figure 1: Unit cell of the 3D cluster, which extends arbitrarily in all three
dimensions. In the absence of errors, the entanglement generated within the
lattice sets up correlation conditions when certain qubits are measured. For
each unit cell of the cluster, quantum correlations guarantee that the
measurement results of the six face qubits (shown above) return an even parity
result [Eq. 1].

This result is a consequence of the quantum correlations established in the
preparation of the cluster. If the cluster is prepared perfectly, these six
qubits are placed into a state that is a $+1$ eigenstate of the operator

$K=\sigma_{x}^{1}\otimes\sigma_{x}^{2}\otimes\sigma_{x}^{3}\otimes\sigma_{x}^{4}\otimes\sigma_{x}^{5}\otimes\sigma_{x}^{6},$
(2)

where $\sigma_{x}$ is the Pauli bit-flip operator. The measurement of each of
these six qubits in the $\sigma_{x}$ basis will produce random results for
each individual qubit. However the eigenvalue condition of this correlation
operator guarantees the classical measurement results satisfy Eq. 1 in the
absence of errors.

The remaining qubits in each unit cell are also measured in the $\sigma_{x}$
basis, but their results are associated with the parity of cells within the
dual lattice [Fig. 2]. This property of the cluster is not important for this
discussion. What is important is that when no quantum algorithm is being
implemented, every qubit is measured in the $\sigma_{x}$ basis and is used to
calculate the parity of their respective cells.

Figure 2: (From Ref. Fowler and Goyal (2009)) The regular structure of the 3D
cluster results in a primal and dual lattice structure. A set of eight unit
cells arranged in a cube results in a complete unit cell present at the
intersection of these eight cells. Hence there are two self-similar lattices
(offset by half a unit cell diagonally) known as the primal and dual lattice.
These two structures are extremely important for computation under the
topological model Raussendorf et al. (2007). However, in the context of this
discussion, the measurement results of the additional nine qubts in Fig. 1 are
associated with the parities of bordering dual cells.

Due to the structure of this 3D cluster state, all error channels can
effectively be mapped into phase errors (Pauli-$\sigma_{z}$ operations applied
to phyical qubits in the lattice which takes a state,
$\alpha{|{0}\rangle}+\beta{|{1}\rangle}\rightarrow\alpha{|{0}\rangle}-\beta{|{1}\rangle}$)
or physical qubit loss Fowler and Goyal (2009). These two distinct channels
are processed slightly differently.

###  II.2 Error channel one: Phase errors

We first consider the effect of phase errors, which act to flip the parity of
a cell of the cluster. As the Pauli operators $\sigma_{x}$ and $\sigma_{z}$
anti-commute, $\sigma_{z}\sigma_{x}=-\sigma_{x}\sigma_{z}$, if a phase error
occurs to one of these six qubits the correlation condition of a cell will
flip from a +1 eigenstate of the operator $K$ to a -1 eigenstate. If the
correlation condition flips to a $-1$ eigenstate of $K$, the classical result
of the six individual measurements also flips to an odd parity condition, i.e.

$(s_{1}+s_{2}+s_{3}+s_{4}+s_{5}+s_{6})\text{ mod }2=1.$ (3)

Errors on qubits on the boundary of each unit cell therefore flip the parity
of the measurement result from even to odd. Note that the change of parity of
any individual cell gives us absolutely no information regarding which one of
the six qubits experienced the physical error.

The second important aspect of this structure is that any given qubit lies on
the boundary of two cells in the cluster. If a given qubit experiences a phase
error it will flip the parity result of the two adjacent cells. This allows us
to detect which of the six qubits of a given cell experienced an error. If a
single cell flips parity, we then examine the parity result of the six
adjacent cells. Assuming that only one error has occured, only one of these
six adjacent cells will have also flipped parity allowing us to uniquely
identify the erred qubit.

Figure 3: (Taken from Ref. Fowler and Goyal (2009)) Illustration of error
effects in the 3D cluster. Here we show a volume $V=4^{3}$ of cluster cells
and the effect of three error chains. As the parity conditions of Eq. 1 are
cyclical (mod 2), the calculation of cell parities only reveals information
regarding the endpoints of error chains. Shown above are three examples, one
error flips the parity of the two cells adjacent to the erred qubit while
longer chains only flip the parity of the end point cells. The goal of error
correction is to faithfully identify these chains given the end point parity
data.

If we now consider more than one error within the lattice, we no longer
identify the location of individual errors but instead identify error chains.
Fig. 3 from Ref. Fowler and Goyal (2009) illustrates. Here we have a 3D
cluster consisting of a cube of $4^{3}$ cells with three error chains. The
first chain is a single error which flips the parity of the two adjacent
cells, the other two chains illustrate the effect of multiple errors. As the
parity conditions are cyclical (mod 2), if two errors occur on the boundaries
of a given cell the parity result will not change. Instead, the two cells at
the endpoints of these error chains are the cells which flip parity.

Hence, in the TCQC model, it is not the locations of individual errors which
are important but the endpoints of error chains. In fact, the symmetries of
the cluster do not require us to identify the physical error chain
corresponding to the detected endpoints. Once the endpoints of the chain are
correctly identified all path of correction operators (Pauli operators which
are applied to reverse detected errors) which connect the two endpoints are
equivalent Raussendorf et al. (2007). Hence, the goal of error correction in
this model is to correctly “pair up” a set of odd parity cells such that the
appropriate correction operators can be applied.

Undetectable errors in this model occur when chains become so long that they
actually connect two boundaries of the lattice. If a physical error chain
completely spans the lattice from one boundary to another then each individual
cell experiences two physical errors and every cell remains in an even parity
state. If the 3D lattice is not used for computation, these error chains are
actually invariants of the cluster and hence have no effect. Once computation
begins, information is stored by deliberately creating holes (or defects) in
this lattice. These defects act as artificial boundaries and consequently
error chains connecting defects to any other boundary (either other defects or
the boundary of the lattice) are undetectable and cause logical errors on
stored information.

From the standpoint of this investigation we are only concerned with
performing active error correction on a defect free lattice. We will not be
introducing information qubits into the cluster. Instead we will be examining
the classical resources required to detect and correctly identify error chains
in an otherwise perfectly prepared lattice.

This type of analysis is justified as information qubits are essentially
regions of the 3D cluster that have simply been removed from the global
lattice. Analyzing the classical requirements for the complete, defect free
lattice therefore represents the maximum amount of classical data that needs
to be processed for correction.

###  II.3 Error channel two: Qubit loss

The second major error channel is qubit loss. As we are motivated by the
optical architecture introduced in Ref. Devitt et al. (2009), loss represents
a significant error channel. Unlike other computation models for quantum
information, the TCQC model can correct loss without additional machinery.
Without going into the details, loss events can be modeled by tracing out the
qubit that is lost from the system and replacing the qubit with the vacuum.
Tracing out the lost qubit is equivalent to measuring the qubit in the
${|{0}\rangle}$ or ${|{1}\rangle}$ state (a $\sigma_{z}$ basis measurement)
with the result unknown. In principal, this type of error can be modeled as a
standard channel, causing the parity of the respective cells to flip with a
probability of 50%. However, since the qubit is no longer present, we can
utilize the vacuum measurement to uniquely identify these error events.

Illustrated in Fig. 4 is the structure of a unit cell when one qubit is
essentially measured out via loss. In this case, the boundary of a cell
increases around the lost qubit. Instead of the parity conditions being
associated with the six face qubits of a given cell, it extends to be the
combined parity of the ten measurements indicated. As the loss event is
detected via no “clicks” from the detector array, this result is corrected by
now taking the parity of this larger structure and proceeding as before.
Provided no other errors have occured, the parity of this larger boundary will
be even, and any additional qubit errors will link this extended cell to a
second end point with odd parity. Recent results, obtained in the context of
the surface code Dennis et al. (2002); Fowler et al. (2008), have demonstrated
a high tolerance to heralded loss events Stace et al. (2009).

Figure 4: The effect of qubit loss on the parity conditions of the cluster.
When a qubit is lost, it is essentially removed from the cluster. The parity
condition of Eq. 1 is extended to the boundary surrounding the loss event. As
a lost qubit is a heralded error (i.e. can be detected separately), the parity
calculation can be modified to encapsulate this larger volume if a loss event
is detected.

##  III The optical computer, a “flowing” network

As introduced in Ref. Devitt et al. (2009), optical TCQC can be performed by
making use of a preparation network of photonic chips Stephens et al. (2008).
This network receives a stream of single photons (from a variety of
appropriate sources) and ejects a fully connected topological cluster. As
computation proceeds via the successive consumption of lattice faces along the
direction of simulated time, the preparation network is designed to
continuously prepare the lattice along this third dimension at a rate equal to
the rate of consumption by the detector layer. Fig. 5 illustrates the basic
design.

Figure 5: General architectural model for a “flowing” optical computer. Single
photon sources inject photonic qubits into a preparation network that
deterministically links up a 3D photonic cluster, layer by layer. Immediately
after the preparation network, an array of single photon detectors measures
each photon to perform computation. As photons are continually linked to the
rear of the 3D cluster as the front is consumed, an arbitrarily deep 3D
cluster can be prepared and consumed with finite space.

Photons are continuously injected into the rear of the preparation network,
ideally from appropriate on-demand sources. Each photon passes through a
network of four photonic chips, which act to link them together into the
appropriate 3D array. Each photonic chip operates on a fundamental clock
cycle, $T$, and each chip in the network operates in a well-defined manner,
independent of the total size of the network Devitt et al. (2009). In total, a
single photon entering the network at $t=0$ will exit at $t=4T$, after which
it can be measured by the detector banks.

Each photonic chip acts to entangle a group of five photons into an
appropriate state such that the parity condition for each cell is satisfied.
After each group of five photons passes through an individual chip, a single
atomic system contained within each chip is measured and reinitialized,
projecting the relevant group of 5-photons into an entangled state. The result
of this atomic measurement is fed forward to the classical processing layer in
order to define a set of initial correlation conditions. The cluster is
defined such that Eq.1 is satisfied for all cells. However, the preparation
network does not automatically produce these correlation conditions. Depending
on the measurement results of the atomic systems contained within each
photonic chip, approximately 50% of cells within the lattice will be prepared
with an initial parity condition that is odd. This can, in principal, be
corrected to be even for all cells by applying selective single qubit
rotations dependent on the atomic readout results, but this is unnecessary.
The initial parity results from the preparation network are simply recorded,
endpoints of error chains are then identified with cells that have changed
parity from this initial state.

As one dimension of the topological lattice is identified as simulated time,
the total 2D cross section defines the actual size of the quantum computer.
Defects, regions of the cluster measured in the $\sigma_{z}$ basis, are used
to define logical qubits and are kept well separated to ensure fault
tolerance. The 2D cross section is then continually teleported, via
measurement, to the next successive layer along the direction of simulated
time allowing an algorithm to be implemented (in a similar manner to standard
cluster state computation Raussendorf and Briegel (2001)).

Figure 6: basic structure of the detection layer in the optical network. A
given unit cell of the cluster can be associated with 9 optical waveguides
containing temporally separated photonic qubits. For each set of 9 detectors
(consisting of a polarizing beam splitter and two single photon detectors for
polarization encoding), the central detector is associated with the cross-
sectional co-ordinate address, $(i,j)$, for the cell. The temporal co-
ordinate, $T$, is associated with the current clock cycle of the quantum
preparation network. For each unit cell, in the absence of photon loss, the
measurement results for the 6 face qubits are sent to the first classical
processing layer that calculates Eq. 4 for each 3D co-ordinate, $(i,j,T)$. If
the parity result differs between co-ordinates $(i,j,T-2)$ and $(i,j,T)$, this
information is sent to the next classical processing layer.

In Fig. 6 we illustrate the structure of the detection system. For the sake of
simplicity, we are assuming that the basis states for the qubits are photon
polarization, ${|{H}\rangle}\equiv{|{0}\rangle}$ and
${|{V}\rangle}\equiv{|{1}\rangle}$, hence the detection system consists of a
polarizing beam splitter (PBS) and two single photon detectors. A given unit
cell flows through a set of nine optical lines such that the relevant parity
is given by,

$P(i,j,T)=(s_{(i,j)}^{T-1}+s_{(i-1,j)}^{T}+s_{(i,j-1)}^{T}+s_{(i,j+1)}^{T}+s_{(i+1,j)}^{T}+s_{(i,j)}^{T+1})\text{
mod }2$ (4)

where $s_{i,j}^{T}$ is the detection result $(1,0)$ of detector $(i,j)$ at
time $T$. This result defines the parity of the cell $(i,j,T)$ in the lattice.
Loss events would result in neither detector firing, at which point the
calculation of Eq. 4 would be redefined based on the loss event to calculate
the parity of the boundary around this lost qubit.

The results of all the detection events are fed directly from the detectors
into the first classical processing layer. This layer calculates Eq. 4 and
passes the result forward to the subsequent processing layer if it differs
from the initial parity. This general structure extends across the entire 2D
cross section of the lattice with parities repeatedly calculated for each unit
cell that flows into the detection system.

##  IV Classical Processing requirements

Illustrated in Fig. 7 is the layer structure of the classical processing for
topological error correction. In total there are four stages, parity
calculation, tree creation, minimum weight matching, and the quantum
controller.

Figure 7: General cross-sectional processing structure for the error
correction procedures in the optical TCQC. The quantum network consists of a
bank of single photon sources, photonic chips and detectors. The preparation
network continually prepares the cluster along the dimension of simulated
time. The detector array will be outputting classical results on the same time
frame as the quantum clock cycle. The classical processing layer is required
to determine likely physical chains of errors producing the classical parity
results detected. The classical layer consists of 4 stages, parity check, co-
ordinate tuple $\rightarrow$ tree creation, minimum weight matching, and the
quantum controller.

As this analysis is only considering the classical requirements for base level
error correction processing, we will not discuss the structure for the quantum
controller. This top-level processor will be responsible for the application
of active quantum algorithms on the topological lattice, given inputs from
both a quantum algorithm compiler, and error data outputted from the
correction processors. In the future, we will be examining the requirements
for this top level processor, but for now we omit details regarding its
structure and operation.

The error correction in this model requires identifying all cells which have
changed parity and reliably identifying pairs of parity changes associated
with a physical error chain. In order for error correction to be effective, we
assume a standard, stochastic, qubit error model. As all standard error
channels (all errors except qubit loss) can be mapped under the topological
model to phase errors Raussendorf et al. (2007); Fowler and Goyal (2009), we
can, without loss of generality, assume that each qubit experiences a phase
error, $\sigma_{z}\equiv Z$, with probability $p$. Therefore, a stochastic
hierarchy exists with respect to longer error chains.

As the probability of a single phase error is given by $p<1$, the probability
of an $d$ error chain is $O(p^{d})\ll 1$. Therefore, for a given set of parity
results, the most likely set of physical errors producing the classical
measurement pattern is the set of end point pairings where the total length of
all connections is minimized.

Classical results stemming from the detection layer are used to calculate the
parity for all unit cells for some total volume. The co-ordinates of all cells
which have experienced a parity flip are stored in a classical data structure.
Minimum weight matching algorithms Chu and Liu (1965); Edmonds (1967); Cook
and Rohe (1999); Kolmogorov (2009) are then used to calculate likely error
chains corresponding to the detected endpoints. Once chains are calculated,
the Pauli frame (the current eigenvalue condition for all cells relative to
their initial state) of the computation, within the quantum controller, is
updated with the new error information.

The frequency of error correction in the lattice is dictated by the
application of the non-Clifford gate

$T=\begin{pmatrix}1&0\\\ 0&e^{\frac{i\pi}{4}}\end{pmatrix}.$ (5)

This gate is required to generate a universal set of operations Nielsen and
Chuang (2000), and in the topological model is achieved via the injection of
multiple, low fidelity, singular ancilla, magic-state distillation Bravyi and
Kitaev (2005); Reichardt (2005) and the application of teleportation protocols
with information qubits. In order to successfully apply logical $T$ gates,
error information must be obtained for the qubit undergoing the teleported $T$
gate prior to application of the correction. Fig. 8 illustrates the
teleportation protocol to implement an $R_{z}(\theta)$ rotation. If a logical
$X$ error exists on the state prior to teleportation, the condition

$R_{z}(\theta)X{|{\phi}\rangle}=XR_{z}(-\theta){|{\phi}\rangle}$ (6)

implies that this error must be known before teleporting the rotation
$R_{z}(\theta)$. If the error is detected after teleportation, the conjugate
rotation $R_{z}(-\theta)$ will actually be applied. Therefore, the classical
processing of the minimum weight matching algorithm will have to occur at a
comparable rate to the logical gate rate of the preparation network to ensure
up-to-date error information for all logical qubits is available when
teleported gates are applied.

Figure 8: Standard teleportation circuit required to perform the rotation
$R_{z}(\theta)$ on an arbitrary quantum state via the preparation of an
appropriate ancilla state. The presence of a bit-flip $\equiv X$ errors on the
qubit affects the gate. Error information during quantum processing must be up
to date upon applying these types of gates in order to ensure rotations are
applied in the correct direction.

As detailed in Ref. Devitt et al. (2007), the clock cycle of the preparation
network can vary from nanoseconds to microseconds, depending on the system
utilized to construct the photonic chip. Hence our goal in this investigation
is to determine, for a given failure probability of the quantum component of
the computer, how quickly the network be operated such that all classical
processing can be performed utilizing today’s technology.

##  V Layers two and three: Minimum weight matching

Calculating the minimum weight matching of the classical parity data stemming
from the first layer of the classical processing network is the essential
requirement for error correction in the topological model. The parity
processing layer is designed to simply output co-ordinate tuples for all
parity changes in the lattice to this next layer. The relevant question is,
can the minimum weight processing of this data be performed over a large
volume of the cluster in a comparable time frame to the quantum preparation
network?

###  V.1 Minimum Weight Matching benchmarking

Classical algorithms for determining the minimum weight matching of a
connected graph are well known with a run-time polynomial in the total number
of nodes Cook and Rohe (1999); Kolmogorov (2009). Such algorithms are derived
from the original Edmonds’ Blossom algorithm Edmonds (1967) and for our
benchmarking tests we have used Blossom V Kolmogorov (2009). However, due to
the nature of our problem, there are several adaptations that can be made to
optimize the algorithm further.

Typical minimum weight matching algorithms accept a list of $N$ co-ordinates,
$N-even$, and of weighted edges (in this case, lattice separation between
nodes) such that the corresponding graph is completely connected. The output
is then a list of edges such that every node is touched by exactly one edge
and the total weight of the edges is a minimum. For the purposes of TCQC we
can optimize by considering the specifics of the problem.

Due to the stochastic hierarchy of errors in the qubit model, and the
assumption that the operational error rate of the computer is low, $p\ll 1$,
the most likely patterns of errors are simply sets of sparse single errors
causing two adjacent cells to flip parity. The probability of obtaining longer
and longer errors chains is increasingly unlikely.

Figure 9: Likely structure of the error data for a large volume of cluster
cells. As we are assuming the operational error rate of the quantum computer
is low, $p\ll 1$, long error chains become increasingly unlikely. Hence, cell
parity flips will most likely be sparse and, generally, pairs of parity flips
will be isolated. This property of the computational model allows a certain
amount of optimization of the classical requirements for minimum weight
matching.

Therefore, for a given volume of classical parity results, erred cells will
tend to be clustered into small groups, as illustrated in Fig. 9.
Additionally, we can consider the computational lattice structure. Fig. 10,
taken from Ref. Devitt et al. (2009), illustrates the 2D cross-section of the
cell structure once logical qubits are defined.

Figure 10: (Taken from Ref. Devitt et al. (2009)). Cross section of a large
topological lattice. Qubits are defined within a cluster region of
approximately $40\times 20$ cells. The actual qubit information is stored in
pairs of defect regions (artificially created holes in the lattice). As
undetectable error chains occur when errors connect two boundary regions,
topological protection is achieved by keeping defect qubits well separated
from boundaries and from each other.

In this example, defects are separated from each other (and from the edge of
the lattice) by a total of 16 cells. Logical errors occur when error chains
connect two boundaries in the cluster. If an error chain spans more than 8
cells, the correction inferred from the endpoints is likely to be incorrect,
resulting in defects connected by a chain of errors - a logical error.

This allows us to set a maximum edge length that is allowed between
connections in the minimum weight matching algorithm. Instead of creating a
completely connected graph structure from the classical data, we instead
create multiple smaller subgraphs, with each subgraph having no connections of
weight greater than a maximum edge parameter $m_{e}$. As the separation and
circumference of defects within the lattice determines the effective distance
of the quantum code $m_{e}$ can safely be chosen such that $m_{e}=\lfloor
d/2\rfloor$. This approximation ensures that all error chains throughout the
lattice with a weight $\leq\lfloor d/2\rfloor$ are connected within the
classical processing layer. This classical approximation is defined to fail if
a single length $>\lfloor d/2\rfloor$ error chain occurs during computation.
This is much less likely than failure of the code itself which can occur as
the result of numerous, not necessarily connected, arrangements of
$\lfloor(d-1)/2\rfloor$ errors.

It should be noted that this approximation does not neglect all error chains
longer than $m_{e}$. However, the classical error correction data has no
knowledge regarding the actual path an error chain has taken through the
lattice. The $m_{e}$ approximation neglects all error chains with endpoints
separated by $>m_{e}$ cells.

By making this approximation, we speed up the classical processing for minimum
weight as, on average, the algorithm will be run on a very sparse graph
structure.

###  V.2 Classical simulations as a function of total cluster volume and code-
distance.

Given the above classical approximation, we have benchmarked the Blossom V
algorithm Kolmogorov (2009) as a function of the total volume of the cluster
for various distances of the quantum code, $d$ and hence $m_{e}$.

In order to investigate the classical processing requirements of the system,
we will assume a physical error rate of the quantum computer. As with previous
investigations into this system we will be assuming, throughout this
discussion, that the quantum computer operates at a physical error rate of
$p=10^{-4}$ Devitt et al. (2009, 2008) and the fault-tolerant threshold is
$p_{th}\approx 0.61\%$ Raussendorf et al. (2007).

Figure 11: Benchmarking data for the tuple $\rightarrow$ tree creation
processing layer. Taken with $10^{4}$ statistical runs, an operational error
rate of $p=10^{-4}$ for various sized codes, $d=(8,10,12,14,16,18,20)$,
$m_{e}=[4,..,10]$. Notice that $m_{e}$ does not significantly alter the
processing time.

Figure 12: Benchmarking data for the minimum weight matching processing layer.
The simulation conditions for this data set are identical to the tree creation
layer shown in Fig. 11.

Given this base assumption, Figs. 11 and 12 examine the processing time of the
modified Blossom V algorithm run on a MacBook Pro (technical details of this
computer are summarized in Appendix. A). For various volume sizes, $V$, from
$35^{3}$ to $295^{3}$ cells, random single qubit $Z$ errors were generated
with a probability of $10^{-4}$. The processing time for each value of $V$ was
examined for different distance quantum codes and hence different values of
the approximation parameter, $m_{e}=d/2$. A list of cell co-ordinate tuples,
$(i,j,T)$, corresponding to the endpoints of error chains (cells with changed
parity) was constructed. This list is the input to the classical processor as,
in practice, it would be provided directly by the hardware.

The tuple data was then processed in two stages. In the first stage, which we
denote as the tree creation layer, an 8-way sort/search tree was created from
the tuple information and then used to generate a list of connections (edges)
between cells and their distances (weights) [Fig. 11]. The second stage of the
simulation applied the Blossom V minimum weight matching algorithm to the
generated sparse graph structures [Fig. 12]. The benchmarking data was taken
using $10^{4}$ runs per data point.

For each cluster volume, code distances $d=[8,10,12,14,16,18,20]$,
corresponding to $m_{e}=[4,..,10]$ were simulated. For both the tuple
$\rightarrow$ tree creation and the minimum weight matching, Figs. 11 and 12
illustrate that the approximation parameter, $m_{e}$, does not significantly
alter the total simulation time and that for a given ($V,m_{e}$), tree
creation and minimum weight matching take a similar amount of time.

###  V.3 Parallelizing the algorithm

The numerical simulations shown in Figs. 11 and 12 clearly illustrate that the
minimum weight matching subroutine cannot be run over the entire lattice used
for TCQC. As a rough estimate, a mainframe device such as the one introduced
in Ref. Devitt et al. (2008) consists of a lattice cross section measuring
$(5\times 10^{5})\times(4\times 10^{3})$ unit cells. Clearly in order to
achieve classical processing speeds of the order of microseconds (for any
distance topological code), either the classical fabrication of the processing
equipment must allow for at least a 10–15 order of magnitude speed up from a
standard Laptop or the application of the tree creation and minimum weight
subroutines must be highly parallelized.

Due to the approximation made to the Blossom V algorithm, parallelizing the
classical processing is possible. The $m_{e}$ approximation to the subroutine
prohibits the establishment of graph connections between two cluster cell co-
ordinates separated by a distance $>m_{e}=d/2$. In Fig. 13 we illustrate the
relative frequency of different sized connected components within the lattice
at an error probability of $p=10^{-4}$, for $m_{e}=[4,..,10]$. These
simulations were performed using the Floyd-Warshall algorithm Floyd (1962);
Warshall (1962) obtained for a volume region of $V=50^{3}$, with $2\times
10^{6}$ statistical runs (resulting in approximately $3\times 10^{7}$
connected components in total). In these simulations, the size of each
connected component in the lattice, $n(m_{e})$, does not represent the longest
path through the graph. Instead it represents the physical edge length through
the cluster of a cube of sufficient size to fully contain each connected
component. In Appendix B we provide additional simulations showing the
distribution of connected components within the cluster to assist in the
explanation of Fig. 13.

Figure 13: Volume independent distribution of connected component sizes for
cluster error data. Shown above is the distribution of the maximum linear size
of each connected component for error data, simulated with $p=10^{-4}$,
$m_{e}=[4,..,10]$ and performed with $2\times 10^{6}$ statistical runs (giving
a total number of connected components $\approx 3\times 10^{7}$). Simulations
were performed using the Floyd-Warshall algorithm Floyd (1962); Warshall
(1962), but instead of calculating the maximum distance between any two nodes
in a connected graph we instead calculate the maximum physical distance
through the cluster (in a single spatial dimension) between any two connected
nodes. These results allow us to estimate the edge length of a cube of
sufficient size to encapsulate all connected components at a given value of
$m_{e}$. Performing an approximate exponential fit to the decay of these
curves allow for the estimation of the probability of obtaining very large
connected components. Appendix B presents further simulation results
explaining the general properties of this curve.

Parallelizing the minimum-weight matching procedure requires subdividing up a
large volume of the cluster into smaller regions such that each instance of
the tuple $\rightarrow$ tree creation and the minimum weight algorithms
faithfully return the same results as processing the entire volume (up to the
failure probability of the computer). In Fig. 13 we provide an approximate
scaling of the decay of each curve, representing the volume independent
relative frequency of connected component with a linear size, $n(m_{e})$, in
the cluster. In order to parallelize classical processing, two regions are
defined. Fig. 14a. illustrates.

The inner volume defines the minimum weight processing region while the outer
volume, with an edge length of $3\times$ the inner volume, defines the tree
creation processing region. During tuple $\rightarrow$ tree creation, if any
connected component contains at least one vertex within the inner volume it is
sent to independent instances of minimum weight matching. Provided that the
edge length of these regions are large enough, then any connected component
with at least one vertex in the inner volume will be fully contained within
the outer volume with high probability.

To determine the size of these processing regions we utilize the decay of the
curves in Fig. 13. The probability of failure when parallelizing classical
processing should be approximately the same as the failure probability of the
quantum computer itself. In order to determine these failure probabilities, we
consider the volume of the cluster required to perform a logical CNOT
operation as a function of $m_{e}$. Fig. 10 illustrates the logical structure
of the lattice. Each logical qubit cell in the cluster consists of a cluster
cross-section measuring $(2d+d/2)(d+d/4)=25m_{e}^{2}/2$ cells. A CNOT gate
requires 4 logical cells and the depth through the cluster required to perform
the gate is $(2d+d/2)=5m_{e}$ cells Raussendorf et al. (2007). Hence the total
cluster volume for a CNOT operation is $V=250m_{e}^{3}$ cells.

The failure probability of the quantum computer during a logical CNOT is
approximately,

$p_{L}(m_{e})\approx 1-(1-{\Omega(m_{e})})^{\lambda(m_{e})}$ (7)

where,

$\Omega(m_{e})\approx\left(\frac{p}{p_{th}}\right)^{d/2}=10^{-2m_{e}}$ (8)

is the probability of failure for a single logical qubit a single layer thick,
with a fault-tolerant threshold of $p_{th}\approx 0.61\%$, $p=10^{-4}$ and
$\lambda(m_{e})=4(2d+d/2)=20m_{e}$ is the number of such layers of the cluster
that need to be consumed to perform a logical CNOT operation.

Given the failure rate of the quantum computer, we utilize the data from Fig.
13 to determine the edge length of a volume large enough to encapsulate all
connected components with a probability approximately equal to Eq. 7. As Fig.
13 represent relative frequencies (the probability of a connected component of
size $n(m_{e})$, relative to a connected component of size one) we scale
$P(n,m_{e})$ by the number of isolated errors expected in a cluster volume
required for a CNOT. Hence,

$6p\times 250m_{e}^{3}P(n,m_{e})=1-(1-{\Omega(m_{e})})^{\lambda(m_{e})}$ (9)

where the factor of 6 comes from the 6 independent qubits per unit cell of the
cluster. Eq. 9 is then solved for $n(m_{e})$ giving,

$n(m_{e})=-\frac{1}{\beta(m_{e})}\ln\left(\frac{1-(1-10^{-2m_{e}})^{20m_{e}}}{0.15\alpha(m_{e})}\right)$
(10)

where $[\alpha(m_{e}),\beta(m_{e})]$ are the scaling parameters shown in Fig.
13.

The values of $n(m_{e})$ for $m_{e}=[4,..10]$ and the probabilities of the
logical CNOT failure and equally the probability of a connected component of
size greater than $n$ are shown in Tab. 1.

$m_{e}$ | CNOT failure | $n(m_{e})$ | $P(\text{connected component }>n)$
---|---|---|---
4 | $O(10^{-7})$ | 10 | $O(10^{-7})$
5 | $O(10^{-8})$ | 15 | $O(10^{-8})$
6 | $O(10^{-10})$ | 23 | $O(10^{-10})$
7 | $O(10^{-12})$ | 32 | $O(10^{-12})$
8 | $O(10^{-14})$ | 44 | $O(10^{-14})$
9 | $O(10^{-16})$ | 62 | $O(10^{-16})$
10 | $O(10^{-18})$ | 81 | $O(10^{-18})$
Table 1: Maximum edge length, $n(m_{e})$, of a cube of sufficient size in the
lattice to encapsulate all connected components of the tuple $\rightarrow$
tree creation graph structure. The last column is the probability that a
connected component of the graph is unbounded by a cube of volume $n^{3}$ and
Eq. 9 ensures that this occurs with approximately the same probability as the
CNOT failure rate of the topological computer.

In Tab. 1 we give the size of the processing regions for parallelizing both
the tuple $\rightarrow$ tree creation and minimum weight matching processes
such that the probability of any connected component within the inner region
unbounded by the boundary of the outer region is approximately the same as the
failure rate of the quantum computer. The value $n(m_{e})$ therefore sets the
edge length of the inner and outer volume regions.

Using this estimate, the tree creation layer becomes an interlaced network,
with each individual instance of tree creation operating over a volume of
$V\approx 27n(m_{e})^{3}$.

Figure 14: Tree creation structure and minimum weight matching processing
structure for parallel application of minimum weight matching. a) illustrates
the volume regions for the two classical processes. For a given approximation
parameter, $m_{e}$, a volume of $27n(m_{e})^{3}$ of tuple data is sent to an
independent tree creation process. Once processed, any subgraph with at least
one vertex in the inner volume region of $n(m_{e})^{3}$ is sent to a separate
instance of minimum weight processing for this region. Parallelization is
achieved by interlacing the outer volumes such that the inner volumes touch.
b) illustrates the temporal processing of this data, where a given tree
creation volume is processed through time. For each instance of the tree
creation process, 67% of the tuple data is taken from the previous instance of
tree creation (as the previous volume overlaps the new volume by two-thirds).
The remaining 33% of the data is collected directly from the measurement of
photons. Therefore both the tree creation process and minimum weight process
must be completed within the time for collection of the new data in order to
keep up with the quantum clock speed.

As we can neglect larger connected components (which occur with probability
roughly equal to the probability of quantum failure), any connected component
that contains at least one vertex within a central volume $V\approx
n(m_{e})^{3}$ will be fully contained within the outer volume of $V\approx
27n(m_{e})^{3}$. The central volume represents the region that is sent to
separate instances of the minimum weight matching algorithm. The tree creation
layer is interlaced such that each of the central volumes touch but do not
overlap.

This processing structure ensures that multiple parallel instances of minimum
weight matching will produce identical results to an individual instance of
minimum weight matching run over the entire volume. As the tree creation
layers are interlaced, tree structures that cross the boundaries of two inner
volumes regions will be sent to two independent instances of minimum weight
matching. After processing, these duplicate results will simply be removed
from the final error list.

We can now combine the results from Tab. 1 with the simulation data of Figs.
11 and 12 to determine the maximum size and speed of a quantum computer such
that error correction data can be processed sufficiently quickly. Fig. 14b.
illustrates how error correction data is collected as qubits along the third
axis of the cluster are sequentially measured. As the tuple $\rightarrow$ tree
creation processing layer consists of an interlaced set of $V=27n(m_{e})^{3}$
cubes, two thirds of the data for any given volume is taken from the
previously collected results while the final one third consists of newly
collected data. Therefore the processing “window” available for each instance
of the tuple $\rightarrow$ tree creation (and hence each instance of minimum
weight matching associated with each tree creation volume) is the time
required to collect this new data.

The optical network illustrated in Sec. III has each parity calculation from
the detector banks, for each unit cell, occurring over three successive
cluster faces and, in the absence of loss, occur every 2$T$, where $T$ is the
separation period of photons (the quantum clock rate). Tree creation from the
parity tuples for a given volume element utilizes the last
$9n(m_{e})^{2}\times 2n(m_{e})$ tuple information from the previous instance
of tree creation and must store the same amount for use in the next tree
creation subroutine. Parity tuple $\rightarrow$ tree creation processing is
repeated for each $27n(m_{e})^{3}$ volume every $2Tn(m_{e})$ seconds.

Taking the simulation data from Fig. 11 (as tuple $\rightarrow$ tree-creation
is the slower of the two processes), the fastest clock cycle,
$T_{\text{min}},$ can be calculated for each value of $m_{e}$ as,

$T_{\text{min}}(m_{e})=\frac{t(3n(m_{e}))}{2n(m_{e})}.$ (11)

where $t(3n(m_{e}))$ is the processing time as a function of the edge length
of the processing volume, $3n(m_{e})$, shown in Fig. 12. The results are shown
in Tab. 2.

$m_{e}$ | CNOT failure | $n(m_{e})$ | $T_{\text{min}}(m_{e})(\mu s)$ | “window”, $2n(m_{e})(\mu s)$ | CNOT operating Freq. | Processing instances / Logical qubit, (I)
---|---|---|---|---|---|---
4 | $O(10^{-7})$ | 10 | 0.06 | 19 | 105 kHz | 8.7
5 | $O(10^{-8})$ | 15 | 0.28 | 31 | 18 kHz | 5.3
6 | $O(10^{-10})$ | 23 | 1.1 | 46 | 4 kHz | 3.4
7 | $O(10^{-12})$ | 32 | 3.2 | 64 | 1 kHz | 2.4
8 | $O(10^{-14})$ | 44 | 9.3 | 87 | 0.3 kHz | 1.7
9 | $O(10^{-16})$ | 62 | 28 | 124 | 0.1 kHz | 1.0
10 | $O(10^{-18})$ | 81 | 68 | 162 | 37 Hz | 0.77
Table 2: Maximum size and speeds for topological quantum computers when
classical processing is performed utilizing the benchmarking data of Figs. 11
and 12. The failure of logical CNOT gates defines the size of the computer,
$\approx 1/KQ$, where $Q$ is the number of logical qubits in the system and
$K$ is the total number of logical time steps available for an algorithm.
$T_{\text{min}}(m_{e})$ defines the maximum speed the quantum network can be
operated such that error correction data can be processed sufficiently
quickly. The processing “window”, independent of the benchmarking data, is
related to the parallelization of classical processing. Processing instances /
Logical qubit defines how many classical processes are required for a lattice
cross section housing one logical qubit.

The last column in Tab. 2 calculates the total number of processing instances
required per logical qubit in the computer. This is calculated as the ratio of
the cross-sectional area of a logical qubit to the cross-sectional area of the
minimum weight matching processing volume.

$I=4\times\frac{(2d+d/2)(d+d/4)}{n(m_{e})^{2}}=4\times\frac{25m_{e}^{2}}{4n(m_{e})^{2}}$
(12)

the factor of 4 is introduced since each instance of minimum weight matching
has an associated tuple $\rightarrow$ tree creation process and that primal
and dual lattice error correction is performed independently giving another
factor of two. As the size of the quantum computer increases (increasing
$m_{e}$) this ratio decreases as the scaling of $n(m_{e})$ is approximately
$n(m_{e})\approx O(m_{e}^{2})$.

While the total size and speed of a topological quantum computer will
ultimately be governed by the experimental accuracy in constructing each
quantum component, the results shown in Tab. 2 are promising. Assuming that
quantum fabrication can reach and accuracy of $p=10^{-4}$, current classical
technology is quite sufficient to process error correction data for a large
range of computer sizes. The logical failure rate of the CNOT gate
approximately defines the size of the computer, $p_{L}(\text{CNOT})\approx
O(1/KQ)$, where $Q$ is the number of logical qubits in the computer and $K$ is
the number of logical time steps in a desired quantum algorithm (note that the
application of non-clifford gates will lower this effective size further).
Even for a small topological computer ($m_{e}=4$ has sufficient protection for
1000 logical qubits running an algorithm requiring approximately $10^{4}$ time
steps) less than ten classical processing instances are required per logical
qubit, a quantum network run at $\approx 17$MHz with a logical CNOT operating
frequency of $\approx 100$kHz.

The classical processing power utilized in this investigation is clearly not
specially designed for the task of operating a topological computer. Not only
can we safely assume that classical processing power will increase before the
advent of a large topological computer, but the design and implementation of
both specialized hardware and more optimal coding should also result in
significant increases in the achievable operational frequency of the quantum
network and logical gates. More recent analysis has suggested that possible
operational frequency of the quantum network could reach the $100$MHz level Su
et al. (2008). In this case, if classical processing could result in a 2-3
order of magnitude speed up when moving to optimized hardware and software,
current classical technology would be sufficient for a quantum computer
capable of a logical error rate $\approx O(10^{-14})$ and a logical CNOT
frequency of $\approx 0.3$MHz.

##  VI Observation and Conclusions

In this work we have focused exclusively on the classical requirements to
perform the underlying error correction processing for the network. As the
error correction procedures can be thought of as the base-level processing,
the development of an appropriate quantum controller system is an obvious next
step. This higher level classical controller will essentially be responsible
for the following,

  1. 1.

The compilation of a user-designed quantum circuit into an appropriate
measurement sequence on a topological cluster.

  2. 2.

Direct control of quantum components within the measurement system of the
topological cluster in order to change the measurement basis for the photon
stream.

  3. 3.

The dynamic allocation of cluster resources dependent on operational error
rate. Specifically, the fundamental partitioning of the lattice into
appropriately separated defect regions for logical qubit storage.

  4. 4.

Accepting the data from the error correction processing layer to faithfully
ensure accurate error correction is performed during computation.

  5. 5.

Dynamical restructuring of the topological lattice partitioning to allow for
ancilla preparation for non-Clifford quantum gates, and optimization of
logical qubit/qubit interactions for specific quantum subroutines.

This last point is one of the more interesting questions that can be addressed
in this model. As we noted in the introduction, once the cluster lattice is
prepared, data processing is performed via software. The structure of the
topological lattice essentially allows for qubit/qubit interactions in a 2D
arrangement [Fig. 10]. However, provided we have access to a large cluster
lattice, we can envisage the dynamical creation of data pathways and “flying
defects” in order to speed up specific quantum subroutines. This could lead to
some extremely interesting avenues of investigation in software control and
optimization of a TCQC architecture.

This analysis has demonstrated that the classical error correction
requirements necessary to construct an optical quantum computer based on
topological cluster states is certainly feasible given today’s technology. We
have illustrated how minimum weight matching, required to process error data
from the topological mainframe, can be optimized in such a way to allow for a
massively parallelized processing network that can process information for
large topological clusters.

These results are very encouraging. As with the quantum preparation network,
the classical front end can also be constructed in a modular manner. As the
quantum preparation network is increased in sized via the addition of more
photonic chips, the classical processing network is also expanded in a similar
way. Parity check processors, tuple $\rightarrow$ tree creation processors and
minimum weight matching processors are also linked into a pre-existing network
as its size expands. The results of this investigation give us a very
optimistic outlook on the viability of the topological model as a possible
avenue to achieve truly large scale quantum computation.

##  VII Acknowledgments

We would like to thank Rod Van Meter, Ashley Stephens, and Zac Evans for
helpful discussions. We acknowledge the support of MEXT, JST, HP and the EU
project HIP and the support of the Australian Research Council, the Australian
Government, and the US National Security Agency (NSA) and the Army Research
Office (ARO) under contract number W911NF-08-1-0527.

##  Appendix A Technical Specifications for simulations.

The technical specifications to the computer used in benchmarking simulations
are summarized below.

Process | Benchmark
---|---
Floating Point Basic | 3.1Gflop/s
vecLib FFT | 3.5 Gflop/s
Memory Fill | 6.2 GB/s
Table 3: Benchmarking for system processes for the MacBook Pro 2.2 GHz, 3GB
RAM Benchmarking data was taken using the program XBench, version 1.3.

##  Appendix B Simulations of graph sizes for cluster errors.

The simulations shown in Fig. 13 illustrate the distribution of the largest
physical distance through the cluster (in a single spatial dimension) between
any two nodes for each connected component for graph structures established
using the $m_{e}$ approximation detailed in the main text. The following
results illustrate the structure of this distribution in more detail.

Figure 15: The maximum graph diameter over $10^{5}$ statistical runs utilizing
$p=10^{-4}$, $m_{e}=6$ and a total cluster volume of $V=100^{3}$. The Floyd-
Warshall algorithm is designed to find the shortest pathway between any two
connected nodes in the cluster and in these simulations we maximize over all
possible connections. Unlike Fig. 13 we are examining the actual graph
diameter, $D$, and not the linear separation of nodes in the physical cluster.
Here we are simply finding the maximum graph diameter in the complete data
set, unlike Fig. 13 which calculates the diameter of all connected components
(hence these results exhibit volume dependence). At $p=10^{-4}$ and $m_{e}=6$,
the graph structure for $D=8$ is the most probable. Changing $p$ shifts which
diameter graph is the most probable, while changing $m_{e}$ changes the values
of $D$ where peaks occur.

Figure 16: Volume independence of distribution of all connected components
within a cluster volume. The upper four curves are simulations calculating the
largest connected component in cluster volumes of
$V=(50^{3},75^{3},100^{3},125^{3})$ while the lower four curves examine the
distribution for all connected components at $p=10^{-4}$ and $m_{e}=6$ (total
number of simulations vary between $O(10^{5})-O(10^{6})$). As you can see,
volume independence when calculating all connected components is good.
Additionally, we are now calculating the maximum physical separation of
endpoints within each connected component. This has the effect of smoothing
out the curves in Fig. 15 and slightly shifting the main peak to the left (as
maximum graph diameter, in general, is larger than the maximum node separation
in the physical cluster). In the simulations calculating the largest connected
component, the main peaks shift to the right as volume increases. This is
again due to the fact that the largest connected component will scale with
volume.

## References

  * Cirac and Zoller (1995) J. Cirac and P. Zoller, Phys. Rev. Lett. 74, 4091 (1995).
  * Cory et al. (1997) D. Cory, A. Fahmy, and T. Havel, Proc. National Academy of Science 94, 1634 (1997).
  * Gershenfeld and Chuang (1997) N. Gershenfeld and I. Chuang, Science 275, 350 (1997).
  * Kane (1998) B. Kane, Nature (London) 393, 133 (1998).
  * Loss and DiVincenzo (1998) D. Loss and D. DiVincenzo, Phys. Rev. A. 57, 120 (1998).
  * Knill et al. (2001) E. Knill, R. Laflamme, and G. Milburn, Nature (London) 409, 46 (2001).
  * Mooij et al. (1999) J. Mooij, T. Orlando, L. Levitov, L. Tian, C. van der Wal, and S. Lloyd, Science 285, 1096 (1999).
  * Nakamura et al. (1999) Y. Nakamura, Y. A. Pashkin, and J. Tsai, Nature (London) 398, 786 (1999).
  * ARDA (2004) ARDA, _Quantum information science and technology roadmap project, http://qist.lanl.gov_ (2004).
  * Kok et al. (2007) P. Kok, W. Munro, K. Nemoto, T. Ralph, J. Dowling, and G. Milburn, Rev. Mod. Phys. 79, 135 (2007).
  * Chiorescu et al. (2003) I. Chiorescu, Y. Nakamura, C. Harmans, and J. Mooij, Science 299, 1869 (2003).
  * Yamamoto et al. (2003) T. Yamamoto, Y. A. Pashkin, O. Astafiev, Y. Nakamura, and J. Tsai, Nature (London) 425, 941 (2003).
  * Chiaverini et al. (2004) J. Chiaverini, D. Leibfried, T. Schaetz, M. Barrett, R. Blakestad, J. Britton, W. Itano, J. Jost, E. Knill, C. Langer, et al., Nature (London) 432, 602 (2004).
  * Häffner et al. (2005) H. Häffner, W. Hänsel, C. Roos, J. Benhelm, D. C. al kar, M. Chwalla, T. Körber, U. Rapol, M. Riebe, P. Schmidt, et al., Nature (London) 438, 643 (2005).
  * Gorman et al. (2005) J. Gorman, D. Hasko, and D. Williams, Phys. Rev. Lett. 95, 090502 (2005).
  * Gaebel et al. (2006) T. Gaebel, M. Domhan, I. Popa, C. Wittmann, P. Neumann, F. Jelezko, J. Rabeau, N. Stavrias, A. Greentree, S. Prawer, et al., Nature Physics (London) 2, 408 (2006).
  * Hanson et al. (2006) R. Hanson, F. Mendoza, R. Epstein, and D. Awschalom, Phys. Rev. Lett. 97, 087601 (2006).
  * Dutt et al. (2007) M. G. Dutt, L. Childress, L. Jiang, E. Togan, J. Maze, F. Jelezko, A. Zibrov, P. Hemmer, and M. Lukin, Science 316, 1312 (2007).
  * O’Brien et al. (2003) J. O’Brien, G. Pryde, A. White, T. Ralph, and D. Branning, Nature (London) 426, 264 (2003).
  * Raussendorf et al. (2007) R. Raussendorf, J. Harrington, and K. Goyal, New J. Phys. 9, 199 (2007).
  * Raussendorf and Harrington (2007) R. Raussendorf and J. Harrington, Phys. Rev. Lett. 98, 190504 (2007).
  * Fowler and Goyal (2009) A. Fowler and K. Goyal, Quant. Inf. Comp. 9, 721 (2009).
  * Devitt et al. (2009) S. Devitt, A. Fowler, A. Stephens, A. Greentree, L. Hollenberg, W. Munro, and K. Nemoto, New. J. Phys. 11, 083032 (2009).
  * Ionicioiu and Munro (2009) R. Ionicioiu and W. Munro, arxiv:0906.1727 (2009).
  * Devitt et al. (2008) S. Devitt, W. Munro, and K. Nemoto, arxiv:0810.2444 (2008).
  * Stephens et al. (2008) A. Stephens, Z. Evans, S. Devitt, A. Greentree, A. Fowler, W. Munro, J. O’Brien, and K. Nemoto, Phys. Rev. A. 78, 032318 (2008).
  * Raussendorf and Briegel (2001) R. Raussendorf and H.-J. Briegel, Phys. Rev. Lett. 86, 5188 (2001).
  * Meter (2006) R. V. Meter, quant-ph/0607065 (2006).
  * Steane (2007) A. Steane, Quant. Inf. Comp. 7, 171 (2007).
  * Bravyi and Kitaev (2001) S. Bravyi and A. Kitaev, Quant. Computers and Computing 2, 43 (2001).
  * Dennis et al. (2002) E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, J. Math. Phys. 43, 4452 (2002).
  * Fowler et al. (2008) A. Fowler, A. Stephens, and P. Groszkowski, arxiv:0803.0272 (2008).
  * Kitaev (1997) A. Kitaev, Russ. Math. Serv. 52, 1191 (1997).
  * Stace et al. (2009) T. Stace, S. Barrett, and A. Doherty, Phys. Rev. Lett. 102, 200501 (2009).
  * Chu and Liu (1965) Y. Chu and T. Liu, Science Sinica 14, 139 (1965).
  * Edmonds (1967) J. Edmonds, J. Res. Nat. Bur. Standards 71B, 233 (1967).
  * Cook and Rohe (1999) W. Cook and A. Rohe, INFORMS Journal on Computing, 11, 138 (1999).
  * Kolmogorov (2009) V. Kolmogorov, Mathematical Programming Computation (2009), URL http://dx.doi.org/10.1007/s12532-009-0002-8.
  * Nielsen and Chuang (2000) M. Nielsen and I. Chuang, _Quantum Computation and Information_ (Cambridge University Press, 2000), 2nd ed.
  * Bravyi and Kitaev (2005) S. Bravyi and A. Kitaev, Phys. Rev. A. 71, 022316 (2005).
  * Reichardt (2005) B. Reichardt, Quant. Inf. Proc. 4, 251 (2005).
  * Devitt et al. (2007) S. Devitt, A. Greentree, R. Ionicioiu, J. O’Brien, W. Munro, and L. Hollenberg, Phys. Rev. A. 76, 052312 (2007).
  * Floyd (1962) R. Floyd, Comm. of the ACM 5, 345 (1962).
  * Warshall (1962) S. Warshall, Journal of the ACM 9, 11 (1962).
  * Su et al. (2008) C.-H. Su, A. Greentree, W. Munro, K. Nemoto, and L. Hollenberg, Phys. Rev. A. 78, 062336 (2008).