Igor L. Markov

Markov's peer-reviewed scholarly work was recognized with five best-paper awards, including four at major conferences and a journal in the field of electronic design automation, and one in theoretical computer science:

• The 2003 IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Donald O. Pederson Best Paper Award, shared with Vivek Shende and John P. Hayes for work[20] on reversible logic circuits.[21]
• The 2004 best-paper award at the Design Automation and Test in Europe (DATE) conference, shared with Smita Krishnaswamy, George F. Viamontes, and John P. Hayes for work[22] on circuit reliability evaluation with probabilistic transfer matrices.[23] Full journal version of this work was published four years later.[24]
• The 2008 best-paper award at the International Symposium on Physical Design (ISPD), shared with Stephen Plaza and Valeria Bertacco, for work[25] on physical synthesis.[26]
• The 2010 best-paper award at the International Conference on Computer-Aided Design (ICCAD) for work[27] on circuit placement.[28] The full journal version of this work was published two years later.[29]
• The best-paper award at the 2012 Alan Turing Centenary Conference in Manchester, UK, shared with Karem A. Sakallah for work[30] on graph automorphism and canonical labeling.[31]

Markov's contributions in quantum computing include

• An algorithm for the synthesis of linear reversible circuits with at most ${\displaystyle O(n^{2}/\log n)}$ CNOT gates (asymptotically optimal)[40] that was extended by Scott Aaronson and Daniel Gottesman to perform optimal synthesis of Clifford circuits,[41] with applications to quantum error correction.
• Optimal synthesis of a two-qubit unitary that uses the minimal number of CNOT gates[42][43]
• Asymptotically optimal synthesis of an ${\displaystyle n}$-qubit quantum circuit that (a) implements a given unitary matrix using no more than${\displaystyle (23/48)\times 4^{n}-(3/2)\times 2^{n}+4/3}$ CNOT gates (less than a factor of two away from the theoretical lower bound) and (b) induces an initial quantum state using no more than ${\displaystyle 2^{n+1}-2n}$ CNOT gates (less than a factor of four away from the theoretical lower bound).[42] IBM Qiskit uses Markov's circuit synthesis algorithm.[44]
• Efficient simulation of quantum circuits with low tree-width using tensor-network contraction.[45] Follow-up works extended this technique with approximations, which allowed them to simulate quantum Fourier transform in poly time.[46][47] Markov's work was used in an essential way in the first proof (by Dorit Aharonov et al.) that quantum Fourier transform can be classically simulated.[46]

Markov's Capo placer[48] provided a baseline for comparisons used in the placement literature. The placer was commercialized and used to design industry chips.[49] Markov's contributions include algorithms, methodologies and software for

• Circuit partitioning:[50][51] high-performance heuristic optimizations for hypergraph partitioning
• Placement:[29][48] algorithms for finding ${\displaystyle (x,y)}$ locations of circuit components that optimize interconnects between those components
• Floorplanning:[52] algorithms and methodologies for chip planning in terms of locations of large components
• Routing:[53] algorithms based on Lagrangian relaxation to construct global wire routs on a multilayer grid structure
• Physical synthesis:[25] algorithms and methodologies for altering logic circuits to admit layouts with shorter interconnects or lower latency