• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


PO is now at the Physics Department of Bielefeld University!

New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

205 submissions , 163 unreviewed
5,075 questions , 2,226 unanswered
5,348 answers , 22,757 comments
1,470 users with positive rep
818 active unimported users
More ...

  Temporally Flat One-Way Quantum Computing

+ 13 like - 0 dislike

I am a physicist at heart, and so I think One-Way Quantum Computing is brilliant. In particular, Graph State Measurement-based Quantum Computing (MBQC) has been a really nice development in Quantum Computing research as originated by Raussendorf & Briegel. One just needs to prepare a multi-partite entangled state as described by a graph, and then perform sequential measurements on each node or qubit (adaptive measurements for deterministic computations).

Another excellent aspect of this approach is that Clifford circuits can be implemented in a single-round of measurements as shown by Raussendorf, Browne and Briegel. These circuits can be classically simulated (efficiently) as shown by Gottesman and Knill so it is an interesting connection between classical simulation and temporal resources.

However, not all temporally flat Graph State MBQC circuits (consisting of one round of measurements) are believed to be simulatable classically. For example, families of circuits in the quantum circuit model consisting of commuting gates called IQP circuits as introduced by Shepherd and Bremner can be implemented in single time-step in MBQC. These IQP circuits are believed not to be classically simulatable (in computational complexity terms, it would lead to a collapse of the polynomial hierarchy).

See also a nice description of a class of circuits implemented in one time-step here. Given that commuting/diagonal unitaries can have some interesting behaviour but non-commuting circuits be classically simulatable. It would be interesting if there were non-commuting circuits that can be implemented but not yet shown to be classically simulatable.

Anyway, my question is:

Are there other interesting circuits that can be implemented in a single time-step in MBQC?

Though I would prefer relations to computational complexity or classical simulation, I would find anything interesting.

Edit: After Joe's excellent answer below, I should clarify a couple of things. As Joe said (and somewhat embarrassingly I have said in one of my own papers), single measurement-round MBQC circuits are in IQP. To be more precise, I am interested in interesting circuits in the problems in IQP that can be implemented in one round of measurements in MBQC. Clifford circuits are an interesting example. If there any other examples which are classically simulatable that would be extremely interesting. Since simulating IQP circuits is believed to be unlikely classically, it would be interesting to find instances of circuits that are.

This post has been migrated from (A51.SE)
asked Nov 7, 2011 in Theoretical Physics by Matty Hoban (435 points) [ no revision ]

2 Answers

+ 8 like - 0 dislike

It doesn't make sense to me to ask about non-commuting operators being implemented in a single time step (though constant depth certainly makes sense). However, you can implement non-commuting gates on the logical subspace of an MBQC which are implemented using commuting measurements on the resource state, though the implemented gates are not deterministic.

Actually, I believe you are viewing IQP more narrowly than you probably should. The answer to your question is that any MBQC which can be implemented in a single measurement layer in MBQC is contained in IQP. This is simply because rather than expressing the result in terms of the logical Hilbert space, you can express it as a series of commuting operations on the physical qubits. Shepherd and Bremner actually deal with this in their paper (in section 5.2 where such operations are called graph-programs).

This post has been migrated from (A51.SE)
answered Nov 8, 2011 by Joe Fitzsimons (3,575 points) [ no revision ]
Thanks, Joe. I was thinking of these graph-programs exactly when talking about IQP and where they showed that every X-program can be implemented by a graph-program. However, one constructs a graph-program in a prescriptive way to perform an X-program. Perhaps my wording in the question is a bit dismissive. I guess my issue with non-commuting gates is to look for an example such as a Clifford circuit which can be implemented in one time-step.

This post has been migrated from (A51.SE)
@Matty: My point is that the Clifford group gates are commuting gates on the physical system, just not in the logical Heisenberg picture that we normally use to look at the computation in an MBQC. Because they are commuting in the physical system, they fall into IQP. It's simply the logical qubits interpretation that is put on top of it that changes things. Fundamentally, any single layer MBQC computation is in IQP for exactly this reason.

This post has been migrated from (A51.SE)
Ah, of course. I get what you mean now. Sorry for being a bit slow. Of course there are also circuits in IQP that cannot be implemented in one time-step in MBQC. Thanks for this point, Joe. My initial motivation was basically to find examples of circuits in IQP that might be of interest - basically for a couple of paragraphs in my thesis.

This post has been migrated from (A51.SE)
I've edited the question to be a bit less vague. Thanks again for your answer though. By the way, I bloody love TP.SE, so thanks for that as well :).

This post has been migrated from (A51.SE)
+ 3 like - 0 dislike

Given the update on the question, I thought it best to post this as a new answer, as it is totally different from my previous answer, and hopefully is interesting.

It seems by the new phrasing of the question that there is a hidden assumption that the MBQC resource state has a number of qubits polynomial in the number of logical qubits. This doesn't necessarily have to be the case, which leads to a potentially interesting situation. It is possible to construct single layer measurement based computations for which the resource state is necessarily exponential in the number of logical qubits, $n$.

To see this, just note that any qubit $j$ in a graph state which is measured in the $X$-$Z$ plane has the same effect as applying the operator $\exp{\big(i \theta \prod_i Z_i \big)}$ where $i$ ranges over all the neighboring qubits of $j$. To see this, note that the entanglement operator applied to $j$ is $|0\rangle\langle 0|\otimes I + |1\rangle\langle 1|\otimes \prod_i Z_i$. As the qubit is initially prepared in state $|+\rangle$ the net result is that the following operator is applied over the neighbouring qubits: $\frac{1}{\sqrt{2}}\left(|0\rangle \otimes I + |1\rangle\otimes \prod_i Z_i\right)$. If the qubit is then rotated by $\exp(i\theta X)$ the result is $\frac{1}{\sqrt{2}}\left(|0\rangle \otimes (\cos \theta I + i \sin \prod_i Z_i) + |1\rangle\otimes (\prod_i Z_i\right)(\cos \theta I + i \sin \prod_i Z_i)$. Thus up to a Pauli correction of $\prod_i Z_i$ we deterministically implement the operator $\cos \theta I + i \sin \prod_i Z_i$ which is just an alternate form of $\exp{\big(i \theta \prod_i Z_i \big)}$.

Note that such operators are the Hadamard transform of the basic building blocks of X-programs, and that all such operators commute independent of which qubits they operate on. IQP is defined in terms of X-programs which are restricted to having a number of terms at most polynomial in the number of qubits. However, there are an exponential number of independent such terms, and so it is possible to specify temporally flat computations which have exponential sized X-programs. Indeed the $n$-input phase Toffoli gate (i.e. the $C....CZ$ gate) is an example of such an operation that requires an exponential number of commuting gates, though it can be achieved with a linear number of non-commuting gates. Thus it is possible to construct single layer measurement based computations which implement X-programs which are exponential in the number of logical qubits, and hence outside of IQP for the logical qubits (though inside IQP for the physical qubits).

Potentially there is a problem here, in that they require an exponential number of parameters to uniquely specify all of the pairs in the X-program. However, if you consider such angles to be generated algorithmically (say with the restriction that each angle can be computed in polynomial time) then it is not even clear whether simulating such a computation can be done in BQP.

This post has been migrated from (A51.SE)
answered Nov 9, 2011 by Joe Fitzsimons (3,575 points) [ no revision ]

Your answer

Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead.
To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL.
Please consult the FAQ for as to how to format your post.
This is the answer box; if you want to write a comment instead, please use the 'add comment' button.
Live preview (may slow down editor)   Preview
Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:
Then drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds).
Please complete the anti-spam verification

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights