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

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
http://arxiv.org/abs/1306.3991

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

• A Rudimentary Quantum Compiler(arxiv abstract)
• “A Rudimentary Quantum Compiler(2cnd Ed.)”(arxiv abstract)
• My webpage for 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 of qubits is untenable as it would require at least gates. This 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 , 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.