IDEAS home Printed from https://ideas.repec.org/p/wop/safiwp/98-04-033.html
   My bibliography  Save this paper

Some Notes on Parallel Quantum Computation

Author

Listed:
  • Cristopher Moore
  • Martin Nilsson

Abstract

We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates can be parallelized to logarithmic depth, while circuits composed of both cannot. Finally, while we note the Quantum Fourier Transform can be parallelized to linear depth, we exhibit a simple quantum circuit related to it that we believe cannot be parallelized to less than linear depth, and therefore might be used to prove that QNC

Suggested Citation

  • Cristopher Moore & Martin Nilsson, 1998. "Some Notes on Parallel Quantum Computation," Working Papers 98-04-033, Santa Fe Institute.
    • Handle: RePEc:wop:safiwp:98-04-033
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    References listed on IDEAS

    as
    1. Frank, Murray & Gencay, Ramazan & Stengos, Thanasis, 1988. "International chaos?," European Economic Review, Elsevier, vol. 32(8), pages 1569-1584, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Manthos D. Delis & Sotirios Kokas & Steven Ongena, 2016. "Foreign Ownership and Market Power in Banking: Evidence from a World Sample," Journal of Money, Credit and Banking, Blackwell Publishing, vol. 48(2-3), pages 449-483, March.
    2. Takala, Kari & Virén, Matti, 1995. "Testing nonlinear dynamics, long memory and chaotic behaviour with macroeconomic data," Research Discussion Papers 9/1995, Bank of Finland.
    3. repec:zbw:bofrdp:1995_009 is not listed on IDEAS
    4. Mario Cerrato & Christian De Peretti & Nick Sarantis, 2007. "A nonlinear panel unit root test under cross section dependence," Documents de recherche 07-12, Centre d'Études des Politiques Économiques (EPEE), Université d'Evry Val d'Essonne.
    5. Franco Bevilacqua & Adriaan van Zon, 2004. "Random walks and non-linear paths in macroeconomic time series: some evidence and implications," Chapters, in: John Foster & Werner Hölzl (ed.), Applied Evolutionary Economics and Complex Systems, chapter 3, Edward Elgar Publishing.
    6. Pedro Albarrán & Raquel Carrasco & Javier Ruiz-Castillo, 2017. "Are Migrants More Productive Than Stayers? Some Evidence From A Set Of Highly Productive Academic Economists," Economic Inquiry, Western Economic Association International, vol. 55(3), pages 1308-1323, July.
    7. Lukas Menkhoff & Mark P. Taylor, 2007. "The Obstinate Passion of Foreign Exchange Professionals: Technical Analysis," Journal of Economic Literature, American Economic Association, vol. 45(4), pages 936-972, December.
    8. Barnett, William A. & Serletis, Apostolos, 2000. "Martingales, nonlinearity, and chaos," Journal of Economic Dynamics and Control, Elsevier, vol. 24(5-7), pages 703-724, June.
    9. Coronado-Ramírez, Semei L. & Porras-Serrano, Jesús & Venegas-Martínez, Francisco, 2011. "Estructuras no lineales en mercados eficientes: el caso IBEX-35," Sección de Estudios de Posgrado e Investigación de la Escuela Superios de Economía del Instituto Politécnico Nacional, in: Perrotini-Hernández, Ignacio (ed.), Economía: Teoría y Métodos, volume 1, chapter 8, pages 116-129, Escuela Superior de Economía, Instituto Politécnico Nacional.
    10. Atif Kafayat, 2014. "Effects of Exchange Rate Instability on Imports and Exports of Pakistan," Acta Universitatis Danubius. OEconomica, Danubius University of Galati, issue 2(2), pages 205-215, April.
    11. Robert Ślepaczuk & Grzegorz Zakrzewski & Paweł Sakowski, 2012. "Investment strategies beating the market. What can we squeeze from the market?," Working Papers 2012-04, Faculty of Economic Sciences, University of Warsaw.
    12. Barnett, William A. & Serletis, Apostolos & Serletis, Demitre, 2015. "Nonlinear And Complex Dynamics In Economics," Macroeconomic Dynamics, Cambridge University Press, vol. 19(8), pages 1749-1779, December.
    13. John Formby & Stefan Norrbin & Ryoichi Sakano, 1992. "The synchronization of business cycles across the European Community," Open Economies Review, Springer, vol. 3(3), pages 233-253, October.
    14. Khurshid M. KIANI & Terry L. KASTENS, 2006. "Using Macro-Financial Variables To Forecast Recessions. An Analysis Of Canada, 1957-2002," Applied Econometrics and International Development, Euro-American Association of Economic Development, vol. 6(3).
    15. Dominique, C-Rene, 2009. "Could Markets' Equilibrium Sets Be Fractal Attractors?," MPRA Paper 13624, University Library of Munich, Germany.
    16. Degiannakis, Stavros, 2004. "Volatility Forecasting: Evidence from a Fractional Integrated Asymmetric Power ARCH Skewed-t Model," MPRA Paper 96330, University Library of Munich, Germany.
    17. Chen, Shu-Heng & Yeh, Chia-Hsuan, 1997. "Toward a computable approach to the efficient market hypothesis: An application of genetic programming," Journal of Economic Dynamics and Control, Elsevier, vol. 21(6), pages 1043-1063, June.
    18. Ibrahim M. Awad & Wael Alazzeh, 2020. "Using currency demand to estimate the Palestine underground economy: An econometric analysis," Palgrave Communications, Palgrave Macmillan, vol. 6(1), pages 1-11, December.
    19. Cheol‐Ho Park & Scott H. Irwin, 2007. "What Do We Know About The Profitability Of Technical Analysis?," Journal of Economic Surveys, Wiley Blackwell, vol. 21(4), pages 786-826, September.
    20. Ignacio Olmeda & Joaquin Pérez, 1995. "Non-linear dynamics and chaos in the Spanish stock market," Investigaciones Economicas, Fundación SEPI, vol. 19(2), pages 217-248, May.
    21. Blake LeBaron, 1994. "Chaos and Nonlinear Forecastability in Economics and Finance," Finance 9411001, University Library of Munich, Germany.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wop:safiwp:98-04-033. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Thomas Krichel (email available below). General contact details of provider: https://edirc.repec.org/data/epstfus.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.