{"topic":"quantum-algorithms-advantage","sort":"top","limit":25,"offset":0,"count":25,"papers":[{"id":"arxiv:1910.11333","kind":"article","title":"Quantum supremacy using a programmable superconducting processor","authors":["Frank Arute","Kunal Arya","Ryan Babbush","Dave Bacon","Joseph C. Bardin","R. Barends","Rupak Biswas","Sergio Boixo","Fernando G. S. L. Brandão","David A. Buell","Brian Burkett","Yu Chen","Zijun Chen","Ben Chiaro","Roberto Collins","William Courtney","Andrew Dunsworth","Edward Farhi","Brooks Foxen","Austin G. Fowler","Craig Gidney","Marissa Giustina","Rob Graff","Keith Guerin","Steve Habegger"],"author_count":77,"year":2019,"published":"2019-10-23","venue":"Nature","cited_by":7735,"doi":"10.1038/s41586-019-1666-5","arxiv_id":"1910.11333","nct_id":null,"source_url":"https://doi.org/10.1038/s41586-019-1666-5","archive_url":"https://space-kitty.com/papers/arxiv:1910.11333","updated":"2019-12-28","pmid":"31645734","pmcid":null,"openalex_id":"W2982169647","pdf_url":"https://www.nature.com/articles/s41586-019-1666-5.pdf","abstract":"This is an updated version of supplementary information to accompany \"Quantum supremacy using a programmable superconducting processor\", an article published in the October 24, 2019 issue of Nature. The main article is freely available at https://www.nature.com/articles/s41586-019-1666-5. Summary of changes since arXiv:1910.11333v1 (submitted 23 Oct 2019): added URL for qFlex source code; added Erratum section; added Figure S41 comparing statistical and total uncertainty for log and linear XEB; new References [1,65]; miscellaneous updates for clarity and style consistency; miscellaneous typographical and formatting corrections.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":"other-oa","is_open_access":true,"peer_reviewed":null,"categories":["Quantum Computing Algorithms and Architecture"],"details":null,"provenance":"openalex+arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2208.02199","kind":"article","title":"Is there evidence for exponential quantum advantage in quantum chemistry?","authors":["Seunghoon Lee","Joonho Lee","Huanchen Zhai","Yu Tong","Alexander M. Dalzell","Ashutosh Kumar","Phillip Helms","Johnnie Gray","Zhi-Hao Cui","Wenyuan Liu","Michael Kastoryano","Ryan Babbush","John Preskill","David R. Reichman","Earl T. Campbell","Edward F. Valeev","Lin Lin","Garnet Kin-Lic Chan"],"author_count":18,"year":2022,"published":"2022-08-03","venue":"Nat Commun 14, 1952 (2023)","cited_by":253,"doi":"10.1038/s41467-023-37587-6","arxiv_id":"2208.02199","nct_id":null,"source_url":"https://arxiv.org/abs/2208.02199","archive_url":"https://space-kitty.com/papers/arxiv:2208.02199","updated":"2022-11-14","pmid":null,"pmcid":null,"openalex_id":"W4362698547","pdf_url":"https://arxiv.org/pdf/2208.02199","abstract":"The idea to use quantum mechanical devices to simulate other quantum systems is commonly ascribed to Feynman. Since the original suggestion, concrete proposals have appeared for simulating molecular and materials chemistry through quantum computation, as a potential ``killer application''. Indications of potential exponential quantum advantage in artificial tasks have increased interest in this application, thus, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation. We conclude that evidence for such an exponential advantage across chemical space has yet to be found. While quantum computers may still prove useful for quantum chemistry, it may be prudent to assume exponential speedups are not generically available for this problem.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["physics.chem-ph","quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:1608.00263","kind":"article","title":"Characterizing Quantum Supremacy in Near-Term Devices","authors":["Sergio Boixo","Sergei V. Isakov","Vadim N. Smelyanskiy","Ryan Babbush","Nan Ding","Zhang Jiang","Michael J. Bremner","John M. Martinis","Hartmut Neven"],"author_count":9,"year":2016,"published":"2016-07-31","venue":"Nature Physics 14, 595-600 (2018)","cited_by":1167,"doi":"10.1038/s41567-018-0124-x","arxiv_id":"1608.00263","nct_id":null,"source_url":"https://arxiv.org/abs/1608.00263","archive_url":"https://space-kitty.com/papers/arxiv:1608.00263","updated":"2017-04-05","pmid":null,"pmcid":null,"openalex_id":"W2482126025","pdf_url":"https://arxiv.org/pdf/1608.00263","abstract":"A critical question for the field of quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of state-of-the-art classical computers, achieving so-called quantum supremacy. We study the task of sampling from the output distributions of (pseudo-)random quantum circuits, a natural task for benchmarking quantum computers. Crucially, sampling this distribution classically requires a direct numerical simulation of the circuit, with computational cost exponential in the number of qubits. This requirement is typical of chaotic systems. We extend previous results in computational complexity to argue more formally that this sampling task must take exponential time in a classical computer. We study the convergence to the chaotic regime using extensive supercomputer simulations, modeling circuits with up to 42 qubits - the largest quantum circuits simulated to date for a computational task that approaches quantum supremacy. We argue that while chaotic states are extremely sensitive to errors, quantum supremacy can be achieved in the near-term with approximately fifty superconducting qubits. We introduce cross entropy as a useful benchmark of quantum circuits which approximates the circuit fidelity. We show that the cross entropy can be efficiently measured when circuit simulations are available. Beyond the classically tractable regime, the cross entropy can be extrapolated and compared with theoretical estimates of circuit fidelity to define a practical quantum supremacy test.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2211.03999","kind":"article","title":"A polynomial-time classical algorithm for noisy random circuit sampling","authors":["Dorit Aharonov","Xun Gao","Zeph Landau","Yunchao Liu","Umesh Vazirani"],"author_count":5,"year":2022,"published":"2022-11-08","venue":"In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)","cited_by":69,"doi":"10.1145/3564246.3585234","arxiv_id":"2211.03999","nct_id":null,"source_url":"https://arxiv.org/abs/2211.03999","archive_url":"https://space-kitty.com/papers/arxiv:2211.03999","updated":"2022-11-08","pmid":null,"pmcid":null,"openalex_id":"W4376639590","pdf_url":"https://arxiv.org/pdf/2211.03999","abstract":"We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. This gives strong evidence that, in the presence of a constant rate of noise per gate, random circuit sampling (RCS) cannot be the basis of a scalable experimental violation of the extended Church-Turing thesis. Our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2005.02464","kind":"article","title":"Boundaries of quantum supremacy via random circuit sampling","authors":["Alexander Zlokapa","Sergio Boixo","Daniel Lidar"],"author_count":3,"year":2020,"published":"2020-05-05","venue":"npj Quantum Information, 9, 36 (2023)","cited_by":55,"doi":"10.1038/s41534-023-00703-x","arxiv_id":"2005.02464","nct_id":null,"source_url":"https://arxiv.org/abs/2005.02464","archive_url":"https://space-kitty.com/papers/arxiv:2005.02464","updated":"2020-10-09","pmid":null,"pmcid":null,"openalex_id":"W3022917190","pdf_url":"https://arxiv.org/pdf/2005.02464","abstract":"Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling, that is beyond the practical reach of modern supercomputers. We examine the constraints of the observed quantum runtime advantage in an extrapolation to circuits with a larger number of qubits and gates. Due to the exponential decrease of the experimental fidelity with the number of qubits and gates, we demonstrate for current fidelities a theoretical classical runtime advantage for circuits deeper than a few hundred gates, while quantum runtimes for cross-entropy benchmarking limit the region of a quantum advantage to a few hundred qubits. However, the quantum runtime advantage boundary in circuit width and depth grows exponentially with respect to reduced error rates, and our work highlights the importance of continued progress along this line. Extrapolations of measured error rates suggest that the limiting circuit size for which a computationally feasible quantum runtime advantage in cross-entropy benchmarking can be achieved approximately coincides with expectations for early implementations of the surface code and other quantum error correction methods. Thus the boundaries of quantum supremacy via random circuit sampling may fortuitously coincide with the advent of scalable, error corrected quantum computing in the near term.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":"cc-by","is_open_access":true,"peer_reviewed":null,"categories":["quant-ph"],"details":null,"provenance":"arxiv+openalex","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:1803.04402","kind":"article","title":"Quantum Supremacy and the Complexity of Random Circuit Sampling","authors":["Adam Bouland","Bill Fefferman","Chinmay Nirkhe","Umesh Vazirani"],"author_count":4,"year":2018,"published":"2018-03-12","venue":null,"cited_by":63,"doi":"10.1038/s41567-018-0318-2","arxiv_id":"1803.04402","nct_id":null,"source_url":"https://arxiv.org/abs/1803.04402","archive_url":"https://space-kitty.com/papers/arxiv:1803.04402","updated":"2018-03-12","pmid":null,"pmcid":null,"openalex_id":"W2790964615","pdf_url":"https://arxiv.org/pdf/1803.04402","abstract":"A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph","cs.CC"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2310.01431","kind":"article","title":"NISQ Computers: A Path to Quantum Supremacy","authors":["Muhammad AbuGhanem","Hichem Eleuch"],"author_count":2,"year":2023,"published":"2023-09-29","venue":"IEEE Access 12, 102941- 102961, (2024)","cited_by":76,"doi":"10.1109/access.2024.3432330","arxiv_id":"2310.01431","nct_id":null,"source_url":"https://arxiv.org/abs/2310.01431","archive_url":"https://space-kitty.com/papers/arxiv:2310.01431","updated":"2023-09-29","pmid":null,"pmcid":null,"openalex_id":"W4400877210","pdf_url":"https://arxiv.org/pdf/2310.01431","abstract":"The quest for quantum advantage, wherein quantum computers surpass the computational capabilities of classical computers executing state-of-the-art algorithms on well-defined tasks, represents a pivotal race in the domain of quantum computing. NISQ (Noisy Intermediate-Scale Quantum) computing has witnessed remarkable advancements, culminating in significant milestones on the journey towards the realization of universal fault-tolerant quantum computers. This transformative turning point, known as quantum supremacy, has been achieved amid a series of breakthroughs, signifying the dawn of the quantum era. Quantum hardware has undergone substantial integration and architectural evolution, contrasting with its nascent stages. In this review, we critically examine the quantum supremacy experiments conducted thus far, shedding light on their implications and contributions to the evolving landscape of quantum computing. Additionally, we endeavor to illuminate a range of cutting-edge proof-of-principle investigations in the realm of applied quantum computing, providing an insightful overview of the current state of applied quantum research and its prospective influence across diverse scientific, industrial, and technological frontiers.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph","cs.AR"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2102.01738","kind":"article","title":"Noise and the frontier of quantum supremacy","authors":["Adam Bouland","Bill Fefferman","Zeph Landau","Yunchao Liu"],"author_count":4,"year":2021,"published":"2021-02-02","venue":"2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 1308-1317","cited_by":38,"doi":"10.1109/focs52979.2021.00127","arxiv_id":"2102.01738","nct_id":null,"source_url":"https://arxiv.org/abs/2102.01738","archive_url":"https://space-kitty.com/papers/arxiv:2102.01738","updated":"2021-06-09","pmid":null,"pmcid":null,"openalex_id":"W3126253572","pdf_url":"https://arxiv.org/pdf/2102.01738","abstract":"Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step forward, but gaps remain between the theory behind these experiments and their actual implementations. In this work we initiate the study of the complexity of quantum random circuit sampling experiments with realistic amounts of noise. Actual quantum supremacy experiments have high levels of uncorrected noise and exponentially decaying fidelities. It is natural to ask if there is any signal of exponential complexity in these highly noisy devices. Surprisingly, we show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction. More formally, so long as the noise rate of the device is below the error detection threshold, we show it is #P-hard to compute the output probabilities of random circuits with a constant rate of noise per gate. This hardness persists even though these probabilities are exponentially close to uniform. Interestingly these hardness results also have implications for the complexity of experiments in a low-noise setting. The issue here is that prior hardness results for computing output probabilities of random circuits are not robust enough to imprecision to connect with the Stockmeyer argument for hardness of sampling from circuits with constant fidelity. We exponentially improve the robustness of prior results to imprecision, both in the cases of Random Circuit Sampling and BosonSampling. In the latter case we bring the proven hardness within a constant factor in the exponent of the robustness required for hardness of sampling for the first time. We then show that our results are in tension with one another -- the high-noise result implies the low-noise result is essentially optimal, even with generalizations of our techniques.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph","cs.CC"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:1612.05903","kind":"article","title":"Complexity-Theoretic Foundations of Quantum Supremacy Experiments","authors":["Scott Aaronson","Lijie Chen"],"author_count":2,"year":2016,"published":"2016-12-18","venue":null,"cited_by":218,"doi":"10.14288/1.0343134","arxiv_id":"1612.05903","nct_id":null,"source_url":"https://arxiv.org/abs/1612.05903","archive_url":"https://space-kitty.com/papers/arxiv:1612.05903","updated":"2016-12-26","pmid":null,"pmcid":null,"openalex_id":"W2949719769","pdf_url":"https://arxiv.org/pdf/1612.05903","abstract":"In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate \"quantum supremacy\": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as possible. First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by the the Quantum AI group at Google. We show that there's a natural hardness assumption, which has nothing to do with sampling, yet implies that no efficient classical algorithm can pass a statistical test that the quantum sampling procedure's outputs do pass. Compared to previous work, the central advantage is that we can now talk directly about the observed outputs, rather than about the distribution being sampled. Second, in an attempt to refute our hardness assumption, we give a new algorithm, for simulating a general quantum circuit with n qubits and m gates in polynomial space and m^O(n) time. We then discuss why this and other known algorithms fail to refute our assumption. Third, resolving an open problem of Aaronson and Arkhipov, we show that any strong quantum supremacy theorem--of the form \"if approximate quantum sampling is classically easy, then PH collapses\"--must be non-relativizing. Fourth, refuting a conjecture by Aaronson and Ambainis, we show that the Fourier Sampling problem achieves a constant versus linear separation between quantum and randomized query complexities. Fifth, we study quantum supremacy relative to oracles in P/poly. Previous work implies that, if OWFs exist, then quantum supremacy is possible relative to such oracles. We show that some assumption is needed: if SampBPP=SampBQP and NP is in BPP, then quantum supremacy is impossible relative to such oracles.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph","cs.CC"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"doi:10.1140/epjqt/s40507-024-00248-8","kind":"article","title":"Full quantum tomography study of Google’s Sycamore gate on IBM’s quantum computers","authors":["M. AbuGhanem","Hichem Eleuch"],"author_count":2,"year":2024,"published":"2024-05-27","venue":"EPJ Quantum Technology","cited_by":31,"doi":"10.1140/epjqt/s40507-024-00248-8","arxiv_id":null,"nct_id":null,"source_url":"https://doi.org/10.1140/epjqt/s40507-024-00248-8","archive_url":"https://space-kitty.com/papers/doi:10.1140/epjqt/s40507-024-00248-8","updated":null,"pmid":null,"pmcid":null,"openalex_id":"W4399049556","pdf_url":null,"abstract":"Abstract The potential of achieving computational hardware with quantum advantage depends heavily on the quality of quantum gate operations. However, the presence of imperfect two-qubit gates poses a significant challenge and acts as a major obstacle in developing scalable quantum information processors. Google’s Quantum AI and collaborators claimed to have conducted a supremacy regime experiment. In this experiment, a new two-qubit universal gate called theSycamoregate is constructed and employed to generate random quantum circuits (RQCs), using a programmable quantum processor with 53 qubits. These computations were carried out in a computational state space of size $9 \\times 10^{15}$ 9×1015 . Nevertheless, even in strictly-controlled laboratory settings, quantum information on quantum processors is susceptible to various disturbances, including undesired interaction with the surroundings and imperfections in the quantum state. To address this issue, we conduct both quantum state tomography (QST) and quantum process tomography (QPT) experiments on Google’sSycamoregate using different artificial architectural superconducting quantum computer. Furthermore, to demonstrate how errors affect gate fidelity at the level of quantum circuits, we design and conduct full QST experiments for the five-qubit eight-cycle circuit, which was introduced as an example of the programability of Google’sSycamorequantum processor. These quantum tomography experiments are conducted in three distinct environments: noise-free, noisy simulation, and on IBM Quantum’s genuine quantum computer. Our results offer valuable insights into the performance of IBM Quantum’s hardware and the robustness ofSycamoregates within this experimental setup. These findings contribute to our understanding of quantum hardware performance and provide valuable information for optimizing quantum algorithms for practical applications.","abstract_license":"CC-BY (publisher license, via OpenAlex)","license":"cc-by","is_open_access":true,"peer_reviewed":null,"categories":["Quantum Computing Algorithms and Architecture"],"details":null,"provenance":"openalex","attribution":"Abstract of \"Full quantum tomography study of Google’s Sycamore gate on IBM’s quantum computers\" by M. AbuGhanem, Hichem Eleuch, https://doi.org/10.1140/epjqt/s40507-024-00248-8, used under its Creative Commons Attribution license (CC-BY); markup removed, otherwise unmodified."},{"id":"arxiv:2104.10523","kind":"article","title":"Tensor Network Quantum Virtual Machine for Simulating Quantum Circuits at Exascale","authors":["Thien Nguyen","Dmitry I. Lyakh","Eugene Dumitrescu","David Clark","Jeff Larkin","Alexander McCaskey"],"author_count":6,"year":2022,"published":"2022-07-09","venue":"ACM Transactions on Quantum Computing","cited_by":32,"doi":"10.1145/3547334","arxiv_id":"2104.10523","nct_id":null,"source_url":"https://doi.org/10.1145/3547334","archive_url":"https://space-kitty.com/papers/arxiv:2104.10523","updated":"2021-04-21","pmid":null,"pmcid":null,"openalex_id":"W3156308080","pdf_url":"https://arxiv.org/pdf/2104.10523","abstract":"The numerical simulation of quantum circuits is an indispensable tool for development, verification and validation of hybrid quantum-classical algorithms on near-term quantum co-processors. The emergence of exascale high-performance computing (HPC) platforms presents new opportunities for pushing the boundaries of quantum circuit simulation. We present a modernized version of the Tensor Network Quantum Virtual Machine (TNQVM) which serves as a quantum circuit simulation backend in the eXtreme-scale ACCelerator (XACC) framework. The new version is based on the general purpose, scalable tensor network processing library, ExaTN, and provides multiple configurable quantum circuit simulators enabling either exact quantum circuit simulation via the full tensor network contraction, or approximate quantum state representations via suitable tensor factorizations. Upon necessity, stochastic noise modeling from real quantum processors is incorporated into the simulations by modeling quantum channels with Kraus tensors. By combining the portable XACC quantum programming frontend and the scalable ExaTN numerical backend we introduce an end-to-end virtual quantum development environment which can scale from laptops to future exascale platforms. We report initial benchmarks of our framework which include a demonstration of the distributed execution, incorporation of quantum decoherence models, and simulation of the random quantum circuits used for the certification of quantum supremacy on the Google Sycamore superconducting architecture.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":"public-domain","is_open_access":true,"peer_reviewed":null,"categories":["Quantum Computing Algorithms and Architecture"],"details":null,"provenance":"openalex+arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"doi:10.1140/epjqt/s40507-025-00405-7","kind":"article","title":"Superconducting quantum computers: who is leading the future?","authors":["M. AbuGhanem"],"author_count":1,"year":2025,"published":"2025-08-19","venue":"EPJ Quantum Technology","cited_by":28,"doi":"10.1140/epjqt/s40507-025-00405-7","arxiv_id":null,"nct_id":null,"source_url":"https://doi.org/10.1140/epjqt/s40507-025-00405-7","archive_url":"https://space-kitty.com/papers/doi:10.1140/epjqt/s40507-025-00405-7","updated":null,"pmid":null,"pmcid":null,"openalex_id":"W4413305859","pdf_url":null,"abstract":"Abstract Superconducting quantum computing has emerged as a leading platform in the pursuit of practical quantum computers, driven by rapid advances from industry, academia, and government initiatives. This review examines the state of superconducting quantum technology, with emphasis on qubit design, processor architecture, scalability, and supporting quantum software. We compare the hardware strategies and performance milestones of key players—including IBM Quantum, Google Quantum AI, Rigetti Computing, Intel Quantum, QuTech, and Oxford Quantum Circuits—highlighting innovations in qubit coherence, control, and system integration. Landmark demonstrations such as quantum supremacy experiments are discussed alongside progress toward real-world applications in the noisy intermediate-scale quantum (NISQ) era. Beyond hardware, attention is given to the broader software and service ecosystem, including quantum programming frameworks, operating environments, and cloud-accessible platforms such as Amazon Braket, Azure Quantum, and OriginQ Cloud, which enable remote access and algorithm development. Persistent challenges in superconducting quantum computing—such as error correction, system stability, and large-scale integration—are assessed in light of emerging approaches aimed at fault-tolerant quantum computing. As the field moves from the NISQ era toward fault-tolerant quantum computing, we capture the defining hardware achievements and characteristics of current superconducting processors, while examining the ongoing efforts and challenges in overcoming NISQ-era limitations. These developments offer critical insights into the path toward scalable quantum systems and their transformative impact on future technologies, while also underscoring the strategic and societal considerations that require balancing innovation with responsible oversight and thoughtful governance.","abstract_license":"CC-BY (publisher license, via OpenAlex)","license":"cc-by","is_open_access":true,"peer_reviewed":null,"categories":["Quantum Information and Cryptography"],"details":null,"provenance":"openalex","attribution":"Abstract of \"Superconducting quantum computers: who is leading the future?\" by M. AbuGhanem, https://doi.org/10.1140/epjqt/s40507-025-00405-7, used under its Creative Commons Attribution license (CC-BY); markup removed, otherwise unmodified."},{"id":"arxiv:1705.00686","kind":"article","title":"No imminent quantum supremacy by boson sampling","authors":["Alex Neville","Chris Sparrow","Raphaël Clifford","Eric Johnston","Patrick M. Birchall","Ashley Montanaro","Anthony Laing"],"author_count":7,"year":2017,"published":"2017-05-01","venue":"Nature Physics 13, 1153-1157 (2017)","cited_by":179,"doi":"10.1038/nphys4270","arxiv_id":"1705.00686","nct_id":null,"source_url":"https://arxiv.org/abs/1705.00686","archive_url":"https://space-kitty.com/papers/arxiv:1705.00686","updated":"2017-05-01","pmid":null,"pmcid":null,"openalex_id":"W2611687835","pdf_url":"https://arxiv.org/pdf/1705.00686","abstract":"It is predicted that quantum computers will dramatically outperform their conventional counterparts. However, large-scale universal quantum computers are yet to be built. Boson sampling is a rudimentary quantum algorithm tailored to the platform of photons in linear optics, which has sparked interest as a rapid way to demonstrate this quantum supremacy. Photon statistics are governed by intractable matrix functions known as permanents, which suggests that sampling from the distribution obtained by injecting photons into a linear-optical network could be solved more quickly by a photonic experiment than by a classical computer. The contrast between the apparently awesome challenge faced by any classical sampling algorithm and the apparently near-term experimental resources required for a large boson sampling experiment has raised expectations that quantum supremacy by boson sampling is on the horizon. Here we present classical boson sampling algorithms and theoretical analyses of prospects for scaling boson sampling experiments, showing that near-term quantum supremacy via boson sampling is unlikely. While the largest boson sampling experiments reported so far are with 5 photons, our classical algorithm, based on Metropolised independence sampling (MIS), allowed the boson sampling problem to be solved for 30 photons with standard computing hardware. We argue that the impact of experimental photon losses means that demonstrating quantum supremacy by boson sampling would require a step change in technology.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2012.09265","kind":"article","title":"Variational Quantum Algorithms","authors":["M. Cerezo","Andrew Arrasmith","Ryan Babbush","Simon C. Benjamin","Suguru Endo","Keisuke Fujii","Jarrod R. McClean","Kosuke Mitarai","Xiao Yuan","Lukasz Cincio","Patrick J. Coles"],"author_count":11,"year":2020,"published":"2020-12-16","venue":"Nature Reviews Physics 3, 625-644 (2021)","cited_by":3362,"doi":"10.1038/s42254-021-00348-9","arxiv_id":"2012.09265","nct_id":null,"source_url":"https://arxiv.org/abs/2012.09265","archive_url":"https://space-kitty.com/papers/arxiv:2012.09265","updated":"2021-10-04","pmid":null,"pmcid":null,"openalex_id":"W3111162498","pdf_url":"https://arxiv.org/pdf/2012.09265","abstract":"Applications such as simulating complicated quantum systems or solving large-scale linear algebra problems are very challenging for classical computers due to the extremely high computational cost. Quantum computers promise a solution, although fault-tolerant quantum computers will likely not be available in the near future. Current quantum devices have serious constraints, including limited numbers of qubits and noise processes that limit circuit depth. Variational Quantum Algorithms (VQAs), which use a classical optimizer to train a parametrized quantum circuit, have emerged as a leading strategy to address these constraints. VQAs have now been proposed for essentially all applications that researchers have envisioned for quantum computers, and they appear to the best hope for obtaining quantum advantage. Nevertheless, challenges remain including the trainability, accuracy, and efficiency of VQAs. Here we overview the field of VQAs, discuss strategies to overcome their challenges, and highlight the exciting prospects for using them to obtain quantum advantage.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph","cs.LG","stat.ML"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:1909.06210","kind":"preprint","title":"Quantum supremacy and random circuits","authors":["Ramis Movassagh"],"author_count":1,"year":2019,"published":"2019-09-11","venue":null,"cited_by":23,"doi":null,"arxiv_id":"1909.06210","nct_id":null,"source_url":"https://arxiv.org/abs/1909.06210","archive_url":"https://space-kitty.com/papers/arxiv:1909.06210","updated":"2020-11-09","pmid":null,"pmcid":null,"openalex_id":"W3080688664","pdf_url":"https://arxiv.org/pdf/1909.06210","abstract":"As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over $50$ quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a $53-$qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard ($\\#P$-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":false,"categories":["quant-ph","cond-mat.str-el","cs.CC","hep-th","math-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2607.04054","kind":"preprint","title":"Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling","authors":["Sangchul Oh"],"author_count":1,"year":2026,"published":"2026-07-04","venue":null,"cited_by":0,"doi":null,"arxiv_id":"2607.04054","nct_id":null,"source_url":"https://arxiv.org/abs/2607.04054","archive_url":"https://space-kitty.com/papers/arxiv:2607.04054","updated":"2026-07-04","pmid":null,"pmcid":null,"openalex_id":"W7167608095","pdf_url":"https://arxiv.org/pdf/2607.04054","abstract":"Random circuit sampling of bitstrings from a Haar-random quantum state is widely believed to be classically intractable, and has therefore been implemented as a primary benchmark for demonstrating quantum advantage. Here, we challenge this premise by proposing an efficient classical frozen-tree sampling algorithm that exploits the conditional scale invariance of Haar-random quantum states [Oh, arXiv:2602.19448]. The frozen-tree sampler draws bitstrings of $n$ qubits in $O(n)$ time per sample. Moreover, its output probability $p_F(x)$ is statistically identical to the probability $p_C(x)$ of a random quantum circuit, since both are independent instances of the same Dirichlet distribution. Consequently, no statistical test acting on samples alone can distinguish the classical frozen-tree sampler from a quantum random circuit. The claimed quantum advantage of random circuit sampling therefore does not withstand scrutiny: its hardness lies not in sampling from the Dirichlet distribution, which is classically efficient, but in identifying a specific circuit realization.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":false,"categories":["quant-ph","cs.CC","math-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2105.05232","kind":"preprint","title":"Benchmarking near-term quantum computers via random circuit sampling","authors":["Yunchao Liu","Matthew Otten","Roozbeh Bassirianjahromi","Liang Jiang","Bill Fefferman"],"author_count":5,"year":2021,"published":"2021-05-11","venue":null,"cited_by":16,"doi":null,"arxiv_id":"2105.05232","nct_id":null,"source_url":"https://arxiv.org/abs/2105.05232","archive_url":"https://space-kitty.com/papers/arxiv:2105.05232","updated":"2022-04-19","pmid":null,"pmcid":null,"openalex_id":"W3163760866","pdf_url":"https://arxiv.org/pdf/2105.05232","abstract":"The increasing scale of near-term quantum hardware motivates the need for efficient noise characterization methods, since qubit and gate level techniques cannot capture crosstalk and correlated noise in many qubit systems. While scalable approaches, such as cycle benchmarking, are known for special classes of quantum circuits, the characterization of noise in general circuits with non-Clifford gates has been an unreachable task. We develop an algorithm that can sample-efficiently estimate the total amount of noise induced by a layer of arbitrary non-Clifford gates, including all crosstalks, and experimentally demonstrate the method on IBM Quantum hardware. Our algorithm is inspired by Google's quantum supremacy experiment and is based on random circuit sampling. In their paper, Google observed that their experimental linear cross entropy was consistent with a simple uncorrelated noise model, and claimed this coincidence indicated that the noise in their device was uncorrelated -- a key step in hardware development towards fault tolerance. As an application, we show that our result provides formal evidence to support such a conclusion.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":false,"categories":["quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2609.29337","kind":"preprint","title":"Nonorthogonal variational quantum simulation for quantum chemistry","authors":["Zongkang Zhang","Jiajun Ren","Xiao Yuan"],"author_count":3,"year":2026,"published":"2026-09-24","venue":null,"cited_by":0,"doi":null,"arxiv_id":"2609.29337","nct_id":null,"source_url":"https://arxiv.org/abs/2609.29337","archive_url":"https://space-kitty.com/papers/arxiv:2609.29337","updated":"2026-09-24","pmid":null,"pmcid":null,"openalex_id":"W7214315677","pdf_url":"https://arxiv.org/pdf/2609.29337","abstract":"Dynamical simulation of quantum many-body systems is a central task in quantum chemistry and requires efficient wavefunction representations. Although tensor-network and neural-network quantum states have achieved considerable success in ground-state calculations, entanglement growth hinders their application to quantum dynamics. Quantum computing may offer a route to quantum advantage, but algorithms such as Trotterization generally require fault-tolerant quantum computers, whereas near-term hardware supports only limited circuit sizes. Variational quantum simulation (VQS) instead represents the evolving state with a single shallow, fixed-size parameterized quantum circuit (PQC). Here, we introduce nonorthogonal variational quantum simulation (NOVQS), which applies linear combinations of parameterized quantum states to real- and imaginary-time evolutions. We design a shallow, hardware-friendly ansatz tailored to second-quantized electronic-structure Hamiltonians, together with resource-efficient protocols for measuring the matrices and vectors in the parameter equations of motion. Error analysis and resource estimation are also provided. Numerical simulations of hydrogen chains and the nitrogen molecule demonstrate that a collection of shallow, or even single-layer, PQCs can match or outperform a much deeper PQC in VQS. In particular, we identify a trade-off between circuit number and depth. NOVQS therefore provides a flexible route to enhancing wavefunction expressivity under circuit-depth constraints, making it a promising framework for quantum dynamics simulations on near-term quantum processors.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":false,"categories":["quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:1610.03632","kind":"preprint","title":"Noise Threshold of Quantum Supremacy","authors":["Keisuke Fujii"],"author_count":1,"year":2016,"published":"2016-10-12","venue":null,"cited_by":16,"doi":null,"arxiv_id":"1610.03632","nct_id":null,"source_url":"https://arxiv.org/abs/1610.03632","archive_url":"https://space-kitty.com/papers/arxiv:1610.03632","updated":"2016-10-12","pmid":null,"pmcid":null,"openalex_id":"W2530250811","pdf_url":"https://arxiv.org/pdf/1610.03632","abstract":"Demonstrating quantum supremacy, a complexity-guaranteed quantum advantage against over the best classical algorithms by using less universal quantum devices, is an important near-term milestone for quantum information processing. Here we develop a threshold theorem for quantum supremacy with noisy quantum circuits in the pre-threshold region, where quantum error correction does not work directly. We show that, even in such a region, we can virtually simulate quantum error correction by postselection. This allows us to show that the output sampled from the noisy quantum circuits (without postselection) cannot be simulated efficiently by classical computers based on a stable complexity theoretical conjecture, i.e., non-collapse of the polynomial hierarchy. By applying this to fault-tolerant quantum computation with the surface codes, we obtain the threshold value $2.84\\%$ for quantum supremacy, which is much higher than the standard threshold $0.75\\%$ for universal fault-tolerant quantum computation with the same circuit-level noise model. Moreover, contrast to the standard noise threshold, the origin of quantum supremacy in noisy quantum circuits is quite clear; the threshold is determined purely by the threshold of magic state distillation, which is essential to gain a quantum advantage.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":false,"categories":["quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2005.06787","kind":"preprint","title":"Classical Simulation of Quantum Supremacy Circuits","authors":["Cupjin Huang","Fang Zhang","Michael Newman","Junjie Cai","Xun Gao","Zhengxiong Tian","Junyin Wu","Haihong Xu","Huanjun Yu","Bo Yuan","Mario Szegedy","Yaoyun Shi","Jianxin Chen"],"author_count":13,"year":2020,"published":"2020-05-14","venue":null,"cited_by":77,"doi":null,"arxiv_id":"2005.06787","nct_id":null,"source_url":"https://arxiv.org/abs/2005.06787","archive_url":"https://space-kitty.com/papers/arxiv:2005.06787","updated":"2020-05-14","pmid":null,"pmcid":null,"openalex_id":"W3025214758","pdf_url":"https://arxiv.org/pdf/2005.06787","abstract":"It is believed that random quantum circuits are difficult to simulate classically. These have been used to demonstrate quantum supremacy: the execution of a computational task on a quantum computer that is infeasible for any classical computer. The task underlying the assertion of quantum supremacy by Arute et al. (Nature, 574, 505--510 (2019)) was initially estimated to require Summit, the world's most powerful supercomputer today, approximately 10,000 years. The same task was performed on the Sycamore quantum processor in only 200 seconds. In this work, we present a tensor network-based classical simulation algorithm. Using a Summit-comparable cluster, we estimate that our simulator can perform this task in less than 20 days. On moderately-sized instances, we reduce the runtime from years to minutes, running several times faster than Sycamore itself. These estimates are based on explicit simulations of parallel subtasks, and leave no room for hidden costs. The simulator's key ingredient is identifying and optimizing the \"stem\" of the computation: a sequence of pairwise tensor contractions that dominates the computational cost. This orders-of-magnitude reduction in classical simulation time, together with proposals for further significant improvements, indicates that achieving quantum supremacy may require a period of continuing quantum hardware developments without an unequivocal first demonstration.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":false,"categories":["quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2002.00035","kind":"article","title":"Simulating quantum chemistry in the seniority-zero space on qubit-based quantum computers","authors":["Vincent E. Elfving","Marta Millaruelo","José A. Gámez","Christian Gogolin"],"author_count":4,"year":2020,"published":"2020-01-31","venue":"Phys. Rev. A 103, 032605 (2021)","cited_by":49,"doi":"10.1103/physreva.103.032605","arxiv_id":"2002.00035","nct_id":null,"source_url":"https://arxiv.org/abs/2002.00035","archive_url":"https://space-kitty.com/papers/arxiv:2002.00035","updated":"2020-11-30","pmid":null,"pmcid":null,"openalex_id":"W3106664997","pdf_url":"https://arxiv.org/pdf/2002.00035","abstract":"Accurate quantum chemistry simulations remain challenging on classical computers for problems of industrially relevant sizes and there is reason for hope that quantum computing may help push the boundaries of what is technically feasible. While variational quantum eigensolver (VQE) algorithms may already turn noisy intermediate scale quantum (NISQ) devices into useful machines, one has to make all efforts to use the scarce quantum resources as efficiently as possible. We combine the so-called seniority-zero, or paired-electron, approximation of computational quantum chemistry with techniques for simulating molecular chemistry on gate-based quantum computers and obtain a very resource efficient quantum simulation algorithm. While some accuracy is lost through the paired-electron approximation, we show that using the freed-up quantum resources for increasing the basis set can lead to more accurate results and reductions in the necessary number of quantum computing runs by several orders of magnitude, already for a simple system like lithium hydride. We also discuss an error mitigation scheme based on post-selection which shows an attractive scaling when the given Hamiltonian format is considered, increasing the viability of its NISQ implementation.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2104.00855","kind":"article","title":"Deep variational quantum eigensolver for excited states and its application to quantum chemistry calculation of periodic materials","authors":["Kaoru Mizuta","Mikiya Fujii","Shigeki Fujii","Kazuhide Ichikawa","Yutaka Imamura","Yukihiro Okuno","Yuya O. Nakagawa"],"author_count":7,"year":2021,"published":"2021-04-02","venue":"Phys. Rev. Research 3, 043121 (2021)","cited_by":25,"doi":"10.1103/physrevresearch.3.043121","arxiv_id":"2104.00855","nct_id":null,"source_url":"https://arxiv.org/abs/2104.00855","archive_url":"https://space-kitty.com/papers/arxiv:2104.00855","updated":"2021-08-27","pmid":null,"pmcid":null,"openalex_id":"W3149257519","pdf_url":"https://arxiv.org/pdf/2104.00855","abstract":"A programmable quantum device that has a large number of qubits without fault-tolerance has emerged recently. Variational Quantum Eigensolver (VQE) is one of the most promising ways to utilize the computational power of such devices to solve problems in condensed matter physics and quantum chemistry. As the size of the current quantum devices is still not large for rivaling classical computers at solving practical problems, Fujii et al. proposed a method called \"Deep VQE\" which can provide the ground state of a given quantum system with the smaller number of qubits by combining the VQE and the technique of coarse-graining [K. Fujii, et al, arXiv:2007.10917]. In this paper, we extend the original proposal of Deep VQE to obtain the excited states and apply it to quantum chemistry calculation of a periodic material, which is one of the most impactful applications of the VQE. We first propose a modified scheme to construct quantum states for coarse-graining in Deep VQE to obtain the excited states. We also present a method to avoid a problem of meaningless eigenvalues in the original Deep VQE without restricting variational quantum states. Finally, we classically simulate our modified Deep VQE for quantum chemistry calculation of a periodic hydrogen chain as a typical periodic material. Our method reproduces the ground-state energy and the first-excited-state energy with the errors up to O(1)% despite the decrease in the number of qubits required for the calculation by two or four compared with the naive VQE. Our result will serve as a beacon for tackling quantum chemistry problems with classically-intractable sizes by smaller quantum devices in the near future.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph","cond-mat.str-el"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2211.04505","kind":"article","title":"Quantifying the effect of gate errors on variational quantum eigensolvers for quantum chemistry","authors":["Kieran Dalton","Christopher K. Long","Yordan S. Yordanov","Charles G. Smith","Crispin H. W. Barnes","Normann Mertig","David R. M. Arvidsson-Shukur"],"author_count":7,"year":2022,"published":"2022-11-08","venue":"npj Quantum Inf 10, 18 (2024)","cited_by":42,"doi":"10.1038/s41534-024-00808-x","arxiv_id":"2211.04505","nct_id":null,"source_url":"https://arxiv.org/abs/2211.04505","archive_url":"https://space-kitty.com/papers/arxiv:2211.04505","updated":"2024-02-13","pmid":null,"pmcid":null,"openalex_id":"W4391275422","pdf_url":"https://arxiv.org/pdf/2211.04505","abstract":"Variational quantum eigensolvers (VQEs) are leading candidates to demonstrate near-term quantum advantage. Here, we conduct density-matrix simulations of leading gate-based VQEs for a range of molecules. We numerically quantify their level of tolerable depolarizing gate-errors. We find that: (i) The best-performing VQEs require gate-error probabilities between $10^{-6}$ and $10^{-4}$ ( $10^{-4}$ and $10^{-2}$ with error mitigation) to predict, within chemical accuracy, ground-state energies of small molecules with $4-14$ orbitals. (ii) ADAPT-VQEs that construct ansatz circuits iteratively outperform fixed-circuit VQEs. (iii) ADAPT-VQEs perform better with circuits constructed from gate-efficient rather than physically-motivated elements. (iv) The maximally-allowed gate-error probability, $p_c$, for any VQE to achieve chemical accuracy decreases with the number $\\ncx$ of noisy two-qubit gates as $p_c\\approxprop\\ncx^{-1}$. Additionally, $p_c$ decreases with system size, even with error mitigation, implying that larger molecules require even lower gate-errors. Thus, quantum advantage via gate-based VQEs is unlikely unless gate-error probabilities are decreased by orders of magnitude.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:1905.00665","kind":"article","title":"Anti-Zeno quantum advantage in fast-driven heat machines","authors":["Victor Mukherjee","Abraham G. Kofman","Gershon Kurizki"],"author_count":3,"year":2019,"published":"2019-05-02","venue":"Commun Phys 3, 8 (2020)","cited_by":41,"doi":"10.1038/s42005-019-0272-z","arxiv_id":"1905.00665","nct_id":null,"source_url":"https://arxiv.org/abs/1905.00665","archive_url":"https://space-kitty.com/papers/arxiv:1905.00665","updated":"2020-01-14","pmid":null,"pmcid":null,"openalex_id":"W2998961059","pdf_url":"https://arxiv.org/pdf/1905.00665","abstract":"Developing quantum machines which can outperform their classical counterparts, thereby achieving quantum supremacy or quantum advantage, is a major aim of the current research on quantum thermodynamics and quantum technologies. Here we show that a fast-modulated cyclic quantum heat machine operating in the non-Markovian regime can lead to significant heat-current and power boosts induced by the anti-Zeno effect. Such boosts signify a quantum advantage over almost all heat-machines proposed thus far that operate in the conventional Markovian regime, where the quantumness of the system-bath interaction plays no role. The present effect owes its origin to the time-energy uncertainty relation in quantum mechanics, which may result in enhanced system-bath energy exchange for modulation periods shorter than the bath correlation-time.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":null,"categories":["quant-ph","cond-mat.stat-mech"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."},{"id":"arxiv:2407.11235","kind":"preprint","title":"Quantum chemistry, classical heuristics, and quantum advantage","authors":["Garnet Kin-Lic Chan"],"author_count":1,"year":2024,"published":"2024-07-15","venue":null,"cited_by":1,"doi":null,"arxiv_id":"2407.11235","nct_id":null,"source_url":"https://arxiv.org/abs/2407.11235","archive_url":"https://space-kitty.com/papers/arxiv:2407.11235","updated":"2024-07-15","pmid":null,"pmcid":null,"openalex_id":"W4403753846","pdf_url":"https://arxiv.org/pdf/2407.11235","abstract":"We describe the problems of quantum chemistry, the intuition behind classical heuristic methods used to solve them, a conjectured form of the classical complexity of quantum chemistry problems, and the subsequent opportunities for quantum advantage. This article is written for both quantum chemists and quantum information theorists. In particular, we attempt to summarize the domain of quantum chemistry problems as well as the chemical intuition that is applied to solve them within concrete statements (such as a classical heuristic cost conjecture and a classification of different avenues for quantum advantage) in the hope that this may stimulate future analysis.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"peer_reviewed":false,"categories":["quant-ph","cond-mat.str-el","physics.chem-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv."}],"next":"https://space-kitty.com/api/v1/topics/quantum-algorithms-advantage/papers?sort=top&limit=25&offset=25"}