Quantum Expanders: Motivation and Construction

by Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma

Theory of Computing, Volume 6(3), pp. 47-79, 2010

Bibliography with links to cited articles

[1]   Jeffrey Adams: Character tables for GL(2),SL(2),PGL(2) and PSL(2) over a finite field.
http://www.math.umd.edu/~jda/characters/characters.pdf, 2002.

[2]   N. Alon and V. D. Milman: λ1, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B, 38(1):73–88, 1985. [Elsevier:10.1016/0095-8956(85)90092-9].

[3]   Noga Alon: Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986. [Springer:90541164662405r4].

[4]   Noga Alon and Yuval Roichman: Random Cayley graphs and expanders. Random Structures Algorithms, 5(2):271–285, 1994. [Wiley:10.1002/rsa.3240050203].

[5]   Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani: Quantum dense coding and quantum finite automata. J. ACM, 49(4):496–511, 2002. [JACM:10.1145/581771.581773].

[6]   Andris Ambainis and Adam Smith: Small pseudo-random families of matrices: Derandomizing approximate quantum encryption. In Proc. 8th Intern. Workshop Randomization and Comput., volume 3122 of LNCS, pp. 249–260. Springer-Verlag, 2004. [doi:10.1007/b99805].

[7]   Robert Beals: Quantum computation of Fourier transforms over symmetric groups. In Proc. 29th STOC, pp. 48–53. ACM Press, 1997. [STOC:10.1145/258533.258548].

[8]   Avraham Ben-Aroya and Amnon Ta-Shma: Quantum expanders and the quantum entropy difference problem. Technical report, arXiv:quant-ph/0702129, 2007. [arXiv:quant-ph/0702129].

[9]   Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson: Randomness conductors and constant-degree lossless expanders. In Proc. 34th STOC, pp. 659–668. ACM Press, 2002. [STOC:10.1145/509907.510003].

[10]   C. M. Dawson and M. A. Nielsen: The Solovay-Kitaev algorithm. Quantum Inf. Comput., 6(1):81–95, 2006.

[11]   Paul Dickinson and Ashwin Nayak: Approximate randomization of quantum states with fewer bits of key. In Proc. AIP Conf., volume 864, pp. 18–36. AIP, 2006.

[12]   Jozef Dodziuk: Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc., 284(2):787–794, 1984. http://www.jstor.org/stable/1999107.

[13]   Joel Friedman: A proof of Alon’s second eigenvalue conjecture. Mem. Amer. Math. Soc., to appear.

[14]   Ofer Gabber and Zvi Galil: Explicit constructions of linear-sized superconcentrators. J. Comput. System Sci., 22(3):407–420, 1981. [JCSS:10.1016/0022-0000(81)90040-4].

[15]   Oded Goldreich and Avi Wigderson: Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Structures Algorithms, 11(4):315–343, 1997. [Wiley:10.1002/(SICI)1098-2418(199712)11:4315::AID-RSA33.0.CO;2-1].

[16]   D. Gross and J. Eisert: Quantum Margulis expanders. Quantum Inf. Comput., 8(8&9):722–733, 2008.

[17]   Joe Harris and William Fulton: Representation Theory. Springer, 1991.

[18]   A.W. Harrow: Quantum expanders from any classical Cayley graph expander. Quantum Inf. Comput., 8(8&9):715–721, 2008.

[19]   M. B. Hastings: Entropy and entanglement in quantum ground states. Phys. Rev. B, 76(3):035114, 2007. [PRB:10.1103/PhysRevB.76.035114].

[20]   M. B. Hastings: Random unitaries give quantum expanders. Phys. Rev. A, 76(3):032315, 2007. [PRA:10.1103/PhysRevA.76.032315].

[21]   M.B. Hastings and A.W. Harrow: Classical and quantum tensor product expanders. Quantum Inf. Comput., 9(3&4):336–360, 2009.

[22]   Schlomo Hoory, Nathan Linial, and Avi Wigderson: Expander graphs and their applications. Bull. Amer. Math. Soc., 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8].

[23]   Shuji Jimbo and Akira Maruoka: Expanders obtained from affine transformations. Combinatorica, 7(4):343–355, 1987. [Springer:6w2126413464n387].

[24]   Nabil Kahale: Eigenvalues and expansion of regular graphs. J. ACM, 42(5):1091–1106, 1995. [JACM:10.1145/210118.210136].

[25]   Martin Kassabov: Symmetric groups and expanders. Electron. Res. Announc. Amer. Math. Soc., 11, 2005.

[26]   Maria Klawe: Limitations on explicit constructions of expanding graphs. SIAM J. Comput., 13(1):156–166, 1984. [SICOMP:10.1137/0213011].

[27]   John D. Lafferty and Daniel Rockmore: Fast Fourier analysis for SL2 over a finite field and related numerical experiments. Experiment. Math., 1(2):115–139, 1992. http://www.expmath.org/restricted/1/1.2/lafferty.ps.gz.

[28]   A. Lubotzky, R. Philips, and P. Sarnak: Ramanujan graphs. Combinatorica, 8(3):261–277, 1988. [Springer:k285687344657q53].

[29]    G. A. Margulis: Explicit constructions of expanders. Problemy Peredachi Informatsii, 9(4):71–80, 1973. http://mi.mathnet.ru/eng/ppi925.

[30]   G. A. Margulis: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51–60, 1988. http://mi.mathnet.ru/eng/ppi686.

[31]   Moshe Morgenstern: Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q. J. Combin. Theory Ser. B, 62(1):44–62, 1994. [Elsevier:10.1006/jctb.1994.1054].

[32]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[33]   A. Nilli: On the second eigenvalue of a graph. Discrete Math., 91(2):207–210, 1991. [Elsevier:10.1016/0012-365X(91)90112-F].

[34]   M. Pinsker: On the complexity of a concentrator. In Proc. 7th Intern. Teletraffic Conf., pp. 318/1–318/4, 1973.

[35]   Sandu Popescu and Daniel Rohrlich: Thermodynamics and the measure of entanglement. Phys. Rev. A, 56(5):3319–3321, 1997. [PRA:10.1103/PhysRevA.56.R3319].

[36]   Omer Reingold, Salil Vadhan, and Avi Wigderson: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. of Math., 155(1):157–187, 2002.

[37]   G. de B. Robinson: On the representations of the symmetric group. Amer. J. Math., 60(3):745–760, 1938. http://www.jstor.org/stable/2371609.

[38]   Amit Sahai and Salil Vadhan: Manipulating statistical difference. In Proc. Randomization Methods in Algorithm Design (DIMACS Workshop, December 1997), volume 43 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 251–270. American Mathematical Society, 1999.

[39]   C. Schensted: Longest increasing and decreasing subsequences. Canad. J. Math., 13(2):179–191, 1961.

[40]   Jean-Pierre Serre: Linear representations of finite groups, volume 42 of Graduate texts in Mathematics. Springer, 1977.

[41]   Salil Vadhan: A Study of Statistical Zero-Knowledge Proofs. PhD thesis, Massachusetts Institute of Technology, 1999.

[42]   John Watrous: Limits on the power of quantum statistical zero-knowledge. In Proc. 43rd FOCS, pp. 459–470. IEEE Comp. Soc. Press, 2002. [FOCS:10.1109/SFCS.2002.1181970].

[43]   John Watrous: Zero-knowledge against quantum attacks. In Proc. 38th STOC, pp. 296–305. ACM Press, 2006. [STOC:10.1145/1132516.1132560].