Transpilers-Compilers
The Perfect Transpiler/Compiler
In Marvel comics, Adam Warlock is a synthetic being who was engineered to be the perfect human. Unlike Captain America, however, whose attributes were amplified pharmacologically to maximum human levels, Adam Warlock’s superhuman abilities are not limited to classical attributes such as strength, dexterity, and constitution. Adam Warlock also possesses cosmic-level abilities that allow him to wield the Infinity Gauntlet without injury (unlike the Hulk) or death (unlike Iron Man). In fact, like Vision in the Marvel Cinematic Universe, who wears the mind stone on his forehead, Adam Warlock usually wears the soul stone on his forehead. Captain America wouldn’t be able to do that.
A Perfect Classical Algorithm…
A paper titled “Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow” by the team of Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, and Maximilian Probst Gutenberg introduces a Captain America algorithm. This classical algorithm approximates solutions to certain problems involving graphs that evolve over time. A key takeaway is that the near-linear solution time is optimal. It is not possible to solve these types of problems any faster.
… With Quantum Applications?
The paper was presented to me by Alain Chancé not as a Captain America algorithm, however, but as an Adam Warlock algorithm. The problems this algorithm solves might be a path toward more efficient transpilers and compilers for quantum computing. In other words, like Adam Warlock, this algorithm might not be limited to classical applications. Transpilers decompose the high-level instructions that simplify quantum circuit design into the instructions that quantum computers can actually execute, while compilers translate those low-level instructions into the schedule of laser pulses or microwave pulses that physically implement the algorithms.
Without getting too technical, transpilers and compilers take the quantum algorithms we design on our laptops, break them down into the instructions that quantum computers can execute, and hopefully optimize these instructions. One way to do this is to represent the quantum circuits as directed acyclic graphs (DAGs) with the nodes representing the gates and the edges representing the dependencies. Non-optimal instructions take longer to execute and generate more errors while optimal instructions take less time to execute and generate fewer errors, so the proposed algorithm may be useful for optimizing such graphs, reducing execution times, and minimizing errors.
Survey Says…
But I don’t write transpilers or compilers, so I can’t write that article. The assertion that the algorithm has quantum applications is more impactful if those who write the transpilers and compilers might consider actually implementing it. Otherwise, this article would read like a comic in which Adam Warlock never leaves his regenerative cocoon: he could come out and save the universe from Thanos, but he isn’t going to.
Fortunately, the algorithm is indeed an Adam Warlock algorithm. My informal “survey” was simply a request to confirm its applicability and potential utility. Responses varied, but the consensus was that the algorithm is indeed applicable to transpilation and/or compilation. The consensus was also that a deeper dive into the paper would be required to determine the algorithm’s utility over current algorithms, which some respondents believe are already quite efficient. But it seems likely, based on the responses, that the algorithm’s optimal time complexity will attract at least some closer scrutiny.
Conclusion
This wasn’t an exhaustive survey and we can’t conclude that the algorithm is already in use in any transpilers or compilers. However, the assertion that this time-optimal classical algorithm has quantum applicability holds up under these informal circumstances. This knowledge might be useful to anyone building their own transpiler/compiler, especially to anyone concerned with the runtime. This is like the Adam Warlock teaser at the end of “Guardians of the Galaxy Vol. 2,” therefore; there is the potential for a great storyline to follow this, but will it?
https://www.deviantart.com/nechtain/art/Adam-Warlock-870861660
