Quantum Bayesian Networks

June 20, 2013

Approximate Quantum Compiling (and “Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas” by Jonathan Welch, Daniel Greenbaum, Sarah Mostame, Alán Aspuru-Guzik)

Filed under: Uncategorized — rrtucci @ 7:18 pm

dishonest scientists, lying, liar, cheating, stealing, unethical, plagiarism, plagiarist, fake, fraud
Check out

“Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas”, by
Jonathan Welch, Daniel Greenbaum, Sarah Mostame, Alán Aspuru-Guzik

Despite it having 4 authors, 3 from Harvard University and 1 from MIT Lincoln Laboratory, and despite having 21 references, this paper does not mention any of my work in this area so let me mention it myself, cause I don’t think anybody else will.

By quantum compiling a unitary matrix, I will mean decomposing that matrix into a sequence of “elementary gates” (i.e., one and two qubit gates). I’ve written several previous posts in this blog about quantum compiling. See here.

The subject of quantum compiling has been of interest to me since about 1998-1999 when I published at arXiv the following two papers and a C++ computer program called Qubiter

In these quantum compiling papers and software, I believe I was the first one to apply something known as the CSD (Cosine Sine Decomposition) to quantum computing, for the task of quantum compiling. The CSD is a very powerful and famous matrix decomposition from linear algebra. Previous papers like the famous one

“Elementary gates for quantum computation”,
by A. Barenco (Oxford), C. H. Bennett (IBM), R. Cleve (Calgary), D. P. DiVincenzo (IBM), N. Margolus (MIT), P. Shor (AT&T), T. Sleator (NYU), J. Smolin (UCLA), H. Weinfurter (Innsbruck)
http://arxiv.org/abs/quant-ph/9503016 (nine authors!, a cast of thousands for a theoretical paper, a paper written by committee?, but not bad at all)

used a different type of matrix decomposition method that is “one-sided” instead of “double-sided” like CSD.

The Harvard-MIT Lincoln Lab paper claims that this 2003 paper by Bullock Markov was the first one to give an exact decomposition of diagonal unitary matrices into elementary gates. That’s false. This Bullock Markov paper repeats the exact decomposition of diagonal unitary gates which was quite explicitly given 5 years earlier in my “Rudimentary Quantum Compiler” papers (see, for example, page 23 in quant-ph/9902062) and which already had been implemented in publicly available software 5 years earlier in Qubiter.

Of course, the idea of exact quantum compiling was only meant to be used for bottle neck steps involving only a small number of qubits in a quantum computer program. Exact compilation of a general unitary matrix acting on a large number n of qubits is untenable as it would require at least (2^n)^2 gates. This (2^n)^2 complexity bound was pointed out in the 1995 Barnett et al “cast of thousands” paper. This complexity bound was probably known much earlier than that and is fairly obvious in retrospect. If it weren’t true, there would be no advantage to quantum computing over classical computing.

The idea of finding approximations to an exact quantum compilation (by dropping some gates that are “not doing much”) is almost as old as the mountains, or at least as old as quantum computing itself. It already shows up prominently in the famous 1994 paper by Don Coppersmith, where, besides inventing his efficient, exact decomposition of the discrete Fourier transform matrix into elementary gates, he also pointed out that if one only wishes to approximately compile the discrete Fourier transform matrix, to within an a priori stipulated error \epsilon, then one can drop many gates from his exact compilation.

I personally have written at least two papers on approximate quantum compiling

  • “Quantum Compiling with Approximation of Multiplexors”
    by Robert R. Tucci, (arxiv abstract)

  • “Oracular Approximation of Quantum Multiplexors and Diagonal Unitary Matrices”, by Robert R. Tucci(arxiv abstract)

Note that the approximate compilation of diagonal unitary matrices is a large part of what I try to do in those papers (I also try to approximate some block-diagonal unitary matrices). Note also that truncating the Walsh transform series as a method of doing approximate quantum compiling is used in quant-ph/0412072 (see for example Eq.(42) in quant-ph/0412072). This is the main approximation method (besides Trotter-Suzuki, which they certainly are not the first to use) used by the Harvard-MIT Lincoln Lab paper. Despite what they imply, this idea is not new. I repeat, truncating the Walsh transform series as a method of doing approximate quantum compiling is not a new idea.

By the way, one kind of approximate compilation of diagonal unitary matrices, the one described in http://arxiv.org/abs/0901.3851, is already implemented in the publicly available software (see “quantum circuit generator” software, in particular, QuanSuite, Quibbs and QOperAv, at my website www-ar-tiste.com). Diagonal unitary matrices arise when one does quantum phase estimation, which is also already implemented in my quantum circuit generator software.



  1. The basterds! When will the QC community give you the recognition you deserve?

    Comment by Max Born — June 20, 2013 @ 9:41 pm

  2. This is an outrage! You should immediately send them email – which will disappear in a spam filter, but still …
    Well, at least the NSA keeps accurate historical records of those things, even if it is all a big secret.
    So for now you have the satisfaction that at least your readers know the truth (although you don’t know who they are and how many of them are spam bots).

    Comment by wb — June 22, 2013 @ 3:31 pm

  3. The fact that you open with the most passive Agressive paragraph, lessons your impact. If someone is whining right off the bat, I’m sure there is reason your work is not taken as seriously as you would like.

    Comment by Heather — June 23, 2013 @ 6:44 pm

  4. Well Miss Heather Mall Queen, The fact that you don’t look at the arxiv evidence (arxiv evidence doesn’t lie and cheat unlike some people from Harvard) and you just spout trash psychology makes me think that you are full of shit. How is that for passive aggressive?

    Comment by rrtucci — June 23, 2013 @ 7:06 pm

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: